NC15743. 好学期来临吧
描述
“只有投入才能获得真正的快乐” —— 鲁迅
SK同学这学期非常忙绿，他刚刚安排好n项工作的进行顺序，就发现BOSS又给了他m项工作，他只好想办法将这m项工作穿插到原来的n项工作之间进行（不改变原来n项工作的相对顺序）。
SK同学如果投入到某项工作中，就会收获一些快乐。之前有n项工作，现在又多了m项工作，本来，应该收获双倍的快乐，但是，SK同学发现自己不能连续投入到两个相邻的工作中。
SK同学想收获尽可能多的快乐，只好请熟练的你来帮助他了~
输入描述
第一行是一个正整数T(≤ 10)，表示测试数据的组数，
对于每组测试数据，
第一行是两个正整数n(≤ 1000)和m(≤ 100)，分别表示原来安排好的n项工作和新增的m项工作，
接下来一行包含n个正整数，表示前n项工作投入时收获的快乐值，
接下来一行包含m个正整数，表示新增的m项工作投入时收获的快乐值，
所有快乐值都不超过100000。
输出描述
对于每组测试数据，输出一行，包含一个整数，表示能收获的快乐值之和的最大值。
示例1
输入:
2 2 2 2 2 1 1 3 2 8 2 7 1 5
输出:
4 20
说明:
对于第一组样例，可以将工作安排成[2,1,2,1],[1,2,1,2],[2,1,1,2]三种方案之一，然后选出2+2来投入。C++ 解法, 执行用时: 82ms, 内存消耗: 892K, 提交时间: 2022-05-06 21:41:35
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+55;
const int M=1e2+55;
const long long INF=1LL<<61;
long long sum[N],dp[2][M][M][2];
int a[N],b[N],n,m;
int main(){
int T;
for(scanf("%d",&T);T--;){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",a+i);
for(int i=1;i<=m;++i) scanf("%d",b+i);
for(int i=0;i<=m;++i) for(int j=0;j<=m;++j)
dp[0][i][j][0]=dp[0][i][j][1]=-INF;
dp[0][0][0][0]=dp[0][0][0][1]=0;
for(int i=1;i<=n;++i) {
int u=i&1;
for(int j=0;j<=m;++j) for(int k=0;k<=m-j;++k){
long long tmp=dp[u^1][j][k][0];
if(k) tmp=max(tmp,dp[u][j][k-1][0]);
dp[u][j][k][1]=tmp;
tmp=max(tmp,dp[u^1][j][k][1]+a[i]);
if(j) tmp=max(tmp,dp[u][j-1][k][1]);
dp[u][j][k][0]=tmp;
}
}
sort(b+1,b+m+1);
for(int i=1;i<=m;++i) sum[i]=sum[i-1]+b[i];
long long ans=0;
for(int i=0;i<=m;++i) ans=max(ans,dp[n&1][m-i][i][0]+sum[m]-sum[i]);
printf("%lld\n",ans);
}
}