題目
http://codeforces.com/problemset/problem/924/c
題意
每天的水位畫(huà)一條線士葫，如果這條線畫(huà)過(guò)了就不用畫(huà)了数苫，告訴你每天在水位之上（嚴(yán)格的上面）有多少條線仪壮，讓你算這幾天在水位之下的線的最小可能總和數(shù)。
樣例
input
6
0 1 0 3 0 2
output
6
第4天水面上有三條線胞四，那么第3天一定劃了線井赌，至少有3條。
水面下的線的數(shù)量為0+0+2+0+3+1=6
思路
- 由題意得第i天水位線的總數(shù)(不包含當(dāng)天水位處的水位線）
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]) - 將得到的水位線總和減去水位之上的水位線總數(shù)
代碼
#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;
}
