【CF1197D】Yet Another Subarray Problem

阳光穿透心脏的1/2处 2023-06-05 08:54 15阅读 0赞

# Description #

[【CF1197D】Yet Another Subarray Problem][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;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11400473.html

[CF1197D_Yet Another Subarray Problem]: https://codeforces.com/problemset/problem/1197/D