CF E69 D dp

Educational Codeforces Round 69 (Rated for Div. 2) D

题目链接

题目大意：

输入一个数组 n m k
求在数组中找一段连续的数求 ∑ai − k * ⌈(r−l+1)/m⌉ 的最大值
显然 r - l + 1 是找的连续的数的长度；
这个题m大小才10
于是长度只要每增加 m 当前答案就会相当于第i-m个减少 k 增加 sum[i] - sum[i-m]；但是 还有一种 ： 就是不接到第i-m后面 也就是说起始点在 i-m ~ i 里
所以可以枚举i-m ~ i 再与接到 i-m 后面（起始点在i-m之前）取个最大值
最后取个答案就完了

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5+5;
int a[maxn];
ll sum[maxn];
ll dp[maxn];
//dp[i]意思是 mod m == i mod m 以i结尾的 答案的最大值
//

int main()
{
   
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1; i <= n; i ++ )
    {
   
        scanf("%d",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    for (int i = 1; i <= n; i ++)
    {
   
        for (int j = 1; j <= m && j <= i; j ++ )//长度在k个以内的
        {
   
            dp[i] = max(dp[i],sum[i] - sum[i-j] - k);
        }
        if(i >= m)
        {
   
            dp[i] = max(dp[i],dp[i-m]+sum[i] - sum[i-m] - k);
        }
    }
    ll ans = 0;
    for (int i = 1;i <= n; i ++ )
    {
   
        ans = max(ans,dp[i]);
    }
    printf("%lld\n",ans);
}

大佬的思路就是nb