cf #924C Riverside Curio(data structure greedy)

题目

http://codeforces.com/problemset/problem/924/c

题意

每天的水位画一条线，如果这条线画过了就不用画了，告诉你每天在水位之上（严格的上面）有多少条线，让你算这几天在水位之下的线的最小可能总和数。

样例

input
6
0 1 0 3 0 2
output
6

第4天水面上有三条线，那么第3天一定划了线，至少有3条。
水面下的线的数量为0+0+2+0+3+1=6

思路

• 由题意得第i天水位线的总数(不包含当天水位处的水位线）t[i]=max(t[i-1],a[i])
• 从后往前遍历能得到t[i]=max(t[i+1]-1,a[i]),在从前往后遍历使之不减t[i]=max(t[i-1],t[i])
• 将得到的水位线总和减去水位之上的水位线总数

代码

#include<bits/stdc++.h>
#define  ll long long
using namespace std;
const int maxn=1e5;
ll a[maxn+10];
ll t[maxn+10];
int main(){
  ll n;
  while(cin>>n){
   ll cnt=0;int pre=0;
   for(int i=0;i<n;i++){
    cin>>a[i];cnt+=a[i];
   }
   ll cur=-1;
   for(int i=n-1;i>=0;i--){
    t[i]=max(cur-1,a[i]);
    if(t[i]<0) t[i]=0;
    cur=t[i];}
    ll ans=0;
    for(int i=0;i<n;i++){
       cur=max(cur,t[i]);
       ans+=cur;
    }
    //cout<<ans<<endl;
    cout<<ans-cnt<<endl;
  }
return 0;
}