一直以為是dp或者搜索之類的，搞了半天發(fā)現(xiàn)并不是qwq….這道題其實應該從一個比較整體的角度來考慮，
首先，我們要最小化每天的d，因為每天的劃線總數(shù)是ti=di+mi+1，因此實際上我們就是要最小化每天的t。
很顯然的，t必須滿足幾個條件：1.t[i]>=t[i-1],總不可能線越劃越少吧。2.t[i]>=m[i]+1,這也是廢話
3.t[i]>=t[I+1]-1,這是因為每天最多因為水位上漲到以前沒有到過的高度最多能增加一條劃線。
在滿足這幾個條件的前提下，我們來考慮如何最小化t
因為有第三條的存在，因此我們肯定是要倒著掃一遍的，否則后面的劃線數(shù)還不存在，怎么比較？
這樣一來，不妨再從前面掃一次以滿足1的要求。

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int m[100005],f[100005]; int main() {int n,i,j,cur;cin>>n;for(i=1;i<=n;i++)scanf("%d",&m[i]);for(i=n,cur=0;i;i--){//這里其實不用cur似乎也行得通cur=max(cur-1,0);//每天可以最多比后一天小1,但是不能為負cur=max(cur,m[i]+1);//同時還必須滿足今天的最小劃線要求f[i]=cur;}long long ans=0;//會爆int...for(i=1,cur=0;i<=n;i++){//這里用cur的好處就是如果f[i]不滿足要求的話,// 并不用去更新他,反正每次cur肯定都是上一天滿足要求下的最小值cur=max(cur,f[i]);ans+=cur;}for(i=1;i<=n;i++)ans-=(m[i]+1);//記得減掉水線上的部分cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的CF 472D Riverside Curio的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。