题目描述

难度分:$2000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$k(0 \leq k \leq min(20,n))$，$x(-10^9 \leq x \leq 10^9)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

你需要把$a$中恰好$k$个数增加$x$，其余数减少$x$。该操作必须恰好执行一次。

在最优操作下，$a$的最大连续子数组和的最大值是多少？注意子数组可以是空的，元素和为$0$。

输入样例

4
4 1 2
2 -1 2 3
2 2 3
-1 2
3 0 5
3 2 4
6 2 -8
4 -1 9 -3 7 -8

输出样例

5
7
0
44

算法

前后缀分解+动态规划

注意到$k \leq 20$，如果比较敏感的话可以很容易想到一个线性DP。以某个$a[i]$为基准，分别考虑前缀数组$[1,i]$有多少个数是加上$x$的，后缀数组$[i+1,n]$有多少个数是加上$x$的。

状态定义

$f_1[i][j]$表示前缀数组$[1,i]$中有$j$个数加上$x$的情况下，以$a[i]$结尾的子数组最大累加和。$f_2[i][j]$表示前缀数组$[i,n]$中有$j$个数加上$x$的情况下，以$a[i]$开头的子数组最大累加和。

状态转移

分别考虑$a[i]$到底是加$x$还是减$x$，先考虑前缀：

1. 如果$i \geq j$，说明前缀数组$[1,i-1]$中可以有$j-1$个数加$x$，若$a[i]$加上$x$，则有状态转移方程$f_1[i][j]=max(f_1[i-1][j-1],0)+a[i]+x$。
2. 如果$i-1 \geq j$，说明前缀数组$[1,i-1]$中就可以有$j$个数加$x$，当前的$a[i]$就不用加$x$了，需要减$x$，此时有状态转移方程$max(0, f_1[i - 1][j]) + a[i] - x$。

同理，后缀也是一样考虑：

1. 如果$n-i \geq j-1$，说明后缀数组$[i+1,n]$中可以有$j-1$个数加$x$，若$a[i]$加上$x$，则有状态转移方程$f_1[i][j]=max(f_2[i+1][j-1],0)+a[i]+x$。
2. 如果$n-i \geq j$，说明后缀数组$[i+1,n]$中就可以有$j$个数加$x$，当前的$a[i]$就不用加$x$了，需要减$x$，此时有状态转移方程$max(0, f_2[i + 1][j]) + a[i] - x$。

前后缀的动态规划做完之后，就开始枚举$i \in [1,n]$，对于每个$i$，枚举前缀$[1,i]$中加$x$的数的个数$left$，那么后缀$[i+1,n]$中加$x$的个数就是$right=k-left$。维护$f_1[i][left]+max(0,f_2[i+1][right])$的最大值即可得到答案，后面之所以要和$0$取个$max$，就是因为$f_2[i+1][right]$有可能是负贡献，可以不要，此时直接以$a[i]$结尾即可。

复杂度分析

时间复杂度

瓶颈在于动态规划的过程，状态数量为$O(nk)$，单次转移的时间复杂度为$O(1)$，因此算法的时间复杂度为$O(nk)$。

空间复杂度

瓶颈在于前后缀两个DP数组，不包括原始输入的数组$a$，仅开辟了有限几个变量，因此额外空间复杂度为$O(nk)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int T, n, k, x;
LL a[N], f1[N][21], f2[N][21];

int main() {
    scanf("%d", &T);
    for(int cases = 1; cases <= T; cases++) {
        scanf("%d%d%d", &n, &k, &x);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            for(int j = 0; j <= k; j++) {
                f1[i][j] = f2[i][j] = -INF;
            }
        }
        f1[0][0] = f2[n + 1][0] = 0;
        for(int j = 1; j <= k; j++) {
            f1[0][j] = -INF;
            f2[n + 1][j] = -INF;
        }
        for(int i = 1; i <= n; i++) {
            f1[i][0] = max(f1[i - 1][0] + a[i] - x, a[i] - x);
            int j = n - i + 1;
            f2[j][0] = max(f2[j + 1][0] + a[j] - x, a[j] - x);
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= min(i, k); j++) {
                if(i - 1 >= j) f1[i][j] = max(0LL, f1[i - 1][j]) + a[i] - x;
                if(i >= j) f1[i][j] = max(f1[i][j], max(0LL, f1[i - 1][j - 1]) + a[i] + x);
            }
        }
        for(int i = n; i >= 1; i--) {
            for(int j = 1; j <= min(n - i + 1, k); j++) {
                if(n - i >= j) f2[i][j] = max(0LL, f2[i + 1][j]) + a[i] - x;
                if(n - i >= j - 1) f2[i][j] = max(f2[i][j], max(0LL, f2[i + 1][j - 1]) + a[i] + x);
            }
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++) {
            for(int left = 0; left <= min(i, k); left++) {
                int right = k - left;
                if(n - i >= right) {
                    ans = max(ans, f1[i][left] + max(0LL, f2[i + 1][right]));
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}