自动搬运

查看原文

来自洛谷，原作者为

	Bulyly 09年在役选手

搬运于2025-08-24 22:52:04，当前版本为作者最后更新于2023-10-30 15:39:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接。

• 一道较为直接的 dp。首先我们要清楚 $b$ 数组的作用，显然可以分为以下两类。第一种是用来当炮灰，就是让我们可以选两个 $a$ 中两个连续的数，第二种是用来作为被选择的数。对于 $b$ 中要选的数，我们贪心的选取最大的数，炮灰用最小的显然最优。

• 定义状态 $f_{i,j,k,0/1}$ 表示对于 $a$ 中的前 $i$ 个数，已经用来 $j$ 个 $b$ 数组中的数，其中有 $k$ 个不是炮灰。有如下转移：

  • 不加入 $b$：

    $f_{i,j,k,0}=\max(f_{i-1,j,k,0},f_{i-1,j,k,1})$。

    $f_{i,j,k,1}=f_{i-1,j,k,0}+a_i$。

  • 加入 $b$：

    要选：$f_{i,j,k,0}=\max(f_{i,j,k,0},f_{i-1,j-1,k-1,0+b_{m-k+1}})$。

    炮灰：$f_{i,j,k,1}=\max(f_{i,j,k,1},f_{i-1,j-1,k,1+a_i})$。

• 如果 $b$ 数组没有用完，显然用完一定不劣。所以我们还要对每个没用完 $b$ 的状态继续仿照上面 dp。

Code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=4e3+10;
int n,m,ans,a[N],b[105],f[2][105][105][2];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	sort(b+1,b+m+1);
	for(int i=1;i<=n;i++) {
		int now=i&1,pre=now^1;
		for(int j=0;j<=m;j++) {
			for(int k=0;k<=j;k++) {
				f[now][j][k][0]=max(f[pre][j][k][1],f[pre][j][k][0]);
				f[now][j][k][1]=f[pre][j][k][0]+a[i];
				if(j&&k) f[now][j][k][0]=max(f[now][j][k][0],f[pre][j-1][k-1][0]+b[m-k+1]);
				if(j-1>=k) f[now][j][k][1]=max(f[now][j][k][1],f[pre][j-1][k][1]+a[i]);
				ans=max({ans,f[now][j][k][0],f[now][j][k][1]});
			} 
		}
	}
	for(int i=n+1;i<=n+m;i++) {
		int now=i&1,pre=now^1;
		for(int j=0;j<=m;j++) {
			for(int k=0;k<=j;k++) {
				if(j) f[now][j][k][0]=max(f[pre][j-1][k][1],f[pre][j-1][k][0]);
				if(j&&k) f[now][j][k][1]=f[pre][j-1][k-1][0]+b[m-k+1];
				ans=max({ans,f[now][j][k][0],f[now][j][k][1]});
			} 
		}
	}
	cout<<ans<<"\n";		
	return 0;
}