【CF1197D】Yet Another Subarray Problem

Description

【CF1197D】Yet Another Subarray Problem

给定一个序列和m,k，求出一个子序列使得$\sum\limits_{i=l}^{r}{a_i}-k\times \lceil \frac{r-l+1}{m}\rceil$最大

特别地，一个长度为0的子序列的答案为0

Solution

一段区间的区间和我们可以通过前缀和实现查询

定义$f[i][j]$表示以i为右端点的子序列，左端点$l$满足$(i-l+1)\mod m=j$时的最大值

那么关于状态转移，我们可以考虑在 $i-m$的位置上分段，然后从前一段转移过来还是只保留当前这一段即可

最后取一个最大值即可

Code

#include <bits/stdc++.h>
namespace shl {
    typedef long long ll;
    int n, m, k;
    ll a[300010], f[300010][12], sum[300010];
    inline ll read() {
        ll ret = 0, op = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') op = -1; 
            c = getchar();
        }
        while (isdigit(c)) {
            ret = (ret << 3) + (ret << 1) + c - '0';
            c = getchar();
        }
        return ret * op;
    }
    using std :: max;
    int main() {
        n = read(); m = read(); k = read();
        for (register int i = 1; i <= n; ++i) {
            a[i] = read();
            sum[i] = sum[i - 1] + a[i];
        }
        ll ans = 0;
        for (register int i = 1; i <= n; ++i) {
            if (i - m >= 0) f[i][0] = max(f[i][0], f[i - m][0] + sum[i] - sum[i - m] - k);
            for (register int j = 1; j < m; ++j) {
                if (i - j >= 0) f[i][j] = max(f[i][j], sum[i] - sum[i - j] - k);
                if (i - m >= 0) f[i][j] = max(f[i][j], f[i - m][j] + sum[i] - sum[i - m] - k);
            }
            for (register int j = 0; j < m; ++j) ans = max(ans, f[i][j]);
        }
        std :: cout << ans;
        return 0;
    }
};
int main() {
    shl :: main();
    return 0;
}