dp+預(yù)處理

dp[i]表示第i天時的水位線有多少條，

然后你會發(fā)現(xiàn)這個dp是有后效性的，當(dāng)?shù)趇天的m[i]>dp[i-1]時就要修改之前的dp值

因此我們預(yù)處理出每一天的至少要多少條水位線，記l[i]為多少條水位線

所以每天至少需要m[i]+1條水位線，然后我們從后往前枚舉，記錄now表示從后推出當(dāng)前的i需要的水位線

l[i]=max(now,m[i]+1)

#include <bits/stdc++.h> #define ll long long using namespace std; ll n,m[100011],dp[100011]; ll l[100011]; int main() {scanf("%lld",&n);for (int i=1;i<=n;i++)scanf("%lld",&m[i]);ll now;now=m[n]+1;for (int i=n;i>=1;i--){now--;now=max(now,m[i]+1);l[i]=now;//同上}dp[1]=1;//第一天肯定有一條水位線for (int i=2;i<=n;i++){dp[i]=dp[i-1];dp[i]=max(dp[i],m[i]+1);dp[i]=max(dp[i],l[i]);}ll ans=0;for (int i=1;i<=n;i++)ans+=dp[i]-1-m[i];//統(tǒng)計水位之下的水位線printf("%lld\n",ans); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huangchenyan/p/11179328.html

總結(jié)

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

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