当前位置: 首页 > 工具软件 > Curio > 使用案例 >

CF957D Riverside Curio

花玄裳
2023-12-01

dp+预处理

dp[i]表示第i天时的水位线有多少条,

然后你会发现这个dp是有后效性的,当第i天的m[i]>dp[i-1]时就要修改之前的dp值

因此我们预处理出每一天的至少要多少条水位线,记l[i]为多少条水位线

所以每天至少需要m[i]+1条水位线,然后我们从后往前枚举,记录now表示从后推出当前的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];//统计水位之下的水位线
    printf("%lld\n",ans);
}

 

转载于:https://www.cnblogs.com/huangchenyan/p/11179328.html

 类似资料:

相关阅读

相关文章

相关问答