题目
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;
}
