神仙dp，膜Claris
题意：给一个长度为$n$的数列，求出不超过k次交换后的最大连续子区间和。
发现交换后的最优答案一定是这样的（0和2的长度可以为0）
0 （ 1 ） 2
答案是标号为1的区间和。
那么就相当于在原数列中下标在0或2的数字可以放入1中，而原来下标在1的数可以拿出来到0或2。
我们设$f_{i, 0/1/2, a, b}$表示现在到第$i$个数，现在划分到的集合已经属于$0/1/2$，其中$0/2$中的数有$a$个被放入1中，$1$中的数有$b$个放入了$0/2$中的最优答案，那么最后的答案$ans = max_{0 leq i leq k, 1leq s leq2}(f_{n, s, i, i})$
然后题解里面就出现了转移方程显然这六个字……
喂，转移方程不显然啊……
对于每一个数有保留在原集合和放入$1/(0,2)$中两种放法。
我们只关心有多少数被放入了1，因为这是最后的答案，那么i到i + 1应当可以直接转移，这中间还对应着集合的变化。
对于要放入1的数,应当使$a$转移到$a + 1$
对于从1中拿出来的数，应当使$b$转移到$b + 1$
具体还是参照代码实现吧(感觉还是和没说一样)，时间复杂度$O(nk^{2})$，在$k$较小的时候有比较优秀的表现。
Code：
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 1e4 + 5; const int M = 12; const ll inf = (ll) 1 << 60; int n, m, d[N]; ll f[N][3][M][M]; inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } template <typename T> inline void chkMax(T &x, T y) { if(y > x) x = y; } int main() { // freopen("btsc6.in", "r", stdin); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &d[i]);; for(int i = 0; i <= n; i++) for(int t = 0; t < 3; t++) for(int a = 0; a <= m; a++) for(int b = 0; b <= m; b++) f[i][t][a][b] = -inf; f[0][0][0][0] = 0LL; for(int i = 0; i < n; i++) for(int a = 0; a <= m; a++) { if(a < m) chkMax(f[i + 1][0][a + 1][0], f[i][0][a][0] + d[i + 1]); chkMax(f[i + 1][0][a][0], f[i][0][a][0]); if(m >= 1) chkMax(f[i + 1][1][a][1], f[i][0][a][0]); chkMax(f[i + 1][1][a][0], f[i][0][a][0] + d[i + 1]); } for(int i = 0; i < n; i++) for(int a = 0; a <= m; a++) for(int b = 0; b <= m; b++) { if(b < m) chkMax(f[i + 1][1][a][b + 1], f[i][1][a][b]); chkMax(f[i + 1][1][a][b], f[i][1][a][b] + d[i + 1]); if(a < m) chkMax(f[i + 1][2][a + 1][b], f[i][1][a][b] + d[i + 1]); chkMax(f[i + 1][2][a][b], f[i][1][a][b]); } for(int i = 0; i < n; i++) for(int a = 0; a <= m; a++) for(int b = a; b <= m; b++) { if(a < m) chkMax(f[i + 1][2][a + 1][b], f[i][2][a][b] + d[i + 1]); chkMax(f[i + 1][2][a][b], f[i][2][a][b]); } ll ans = 0LL; for(int i = 0; i <= m; i++) { chkMax(ans, f[n][1][i][i]); chkMax(ans, f[n][2][i][i]); } printf("%lld ", ans); return 0; }