526互联

codeforces 1796D Maximum Subarray

发布时间 2023-04-05 22:23:42作者: 冯文健

https://codeforces.com/problemset/problem/1796/D

解题思路

最大子序列问题的变种。记 f[i][j][p] 表示当前i个元素中有j个元素增加x时，以i结尾并且包含p个元素增加x的子序列的最大值。

f[i][j][p] = max(f[i-1][j-1][p-1] + a[i] +x, f[i-1][j][p] + a[i] - x)。当p == 0和p == 1时，是有可能构成单个元素的子序列的，单独讨论。

#include <bits/stdc++.h>
using namespace std;
#define N 200001

int t, n, k, visit[N][21][21];
int64_t dp[21][21], x, a[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> k >> x;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int p = 0; p <= j; p++) {
                    visit[i][j][p] = 0;
                }
            }
        }
        visit[0][0][0] = 1;
        dp[0][0] = 0;
        int64_t ans = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = min(i,k); j >= 0; j--) {
                if (n - i < k - j) {
                    continue;
                }
                for (int p = j; p >= 0; p--) {
                    int64_t tmp = INT64_MIN;
                    if (p == 0 && i - 1 >= j) {
                        visit[i][j][p] = 1;
                        tmp = max(tmp, a[i] - x);
                    }
                    if (p == 1) {
                        visit[i][j][p] = 1;
                        tmp = max(tmp, a[i] + x);
                    }
                    if (j > 0 && p > 0 && visit[i-1][j-1][p-1] == 1) {
                        visit[i][j][p] = 1;
                        tmp = max(tmp, dp[j-1][p-1] + x + a[i]);
                    }

                    if (visit[i-1][j][p] == 1) {
                        visit[i][j][p] = 1;
                        tmp = max(tmp, dp[j][p] - x + a[i]);
                    }
                    /*
                    if (visit[i][j][p] == 1) {
                        cout << i << " " << j << " " << p << " " << tmp << endl;
                    }
                    */
                    dp[j][p] = tmp;
                    ans = max(ans, tmp);
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}