自动搬运

查看原文

来自洛谷，原作者为

	良心WA题人 啦叭叭叭 啾啾啾啦叭叭叭

搬运于2025-08-24 22:55:14，当前版本为作者最后更新于2024-01-12 15:54:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先发现每种小团体独立。

对于每一个小团体，将选出来的两个学生看成线段的左右端点后，任意两对学生不会相交。因为若两对学生 $(pl,pr)$ 和 $(ql,qr)$ 满足 $p_l\le q_l\le p_r\le q_r$，则选出 $(p_l,q_l)$ 和 $(p_r,q_r)$ 显然更优（将贡献写出来后读者自证不难）。

我们将贡献拆开变成 $a_i-x\times i+a_j+x\times j$。于是对于每个小团体 dp 算出 $f_{i,j,0/1}$ 表示该小团体前 $i$ 个点用 $j$ 次信息学名额，当前是完整匹配/剩余了一个待匹配点的最小不满值。

具体的，$f_{i,j,0}=\min(f_{i-1,j-1,0},f_{i-1,j,1}+a_i+x\times i)$ 表示当前点不选花费一次名额则直接继承，或者当前点用待匹配的一半匹配上。同理，$f_{i,j,1}=\min(f_{i-1,j-1,1},f_{i-1,j,0}+a_i-x\times i)$。

然后考虑在外面使用背包。令 $g_{i,j}$ 表示考虑前 $i$ 个小团体用 $j$ 个名额的最小不满值。直接分组背包即可。因为所有颜色的个数和为 $n$，所以背包合并的时间复杂度为 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=5004;
vector<int>t[NN];
int a[NN],c[NN];
ll f[NN][NN][2],g[NN][NN];
int main()
{
	int n,m,d,x;
	scanf("%d%d%d%d",&n,&m,&d,&x);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		t[c[i]].push_back(i);
	}
	memset(g,0x3f,sizeof(g));
	g[0][0]=0;
	int cnt=0;
	for(int i=1;i<=d;i++)
	{
		for(int j=0;j<=t[i].size();j++)
			for(int k=0;k<=m;k++)
				f[j][k][0]=f[j][k][1]=1e18;
		f[0][0][0]=0;
		for(int j=1;j<=t[i].size();j++)
			for(int k=0;k<=m;k++)
			{
				f[j][k][0]=f[j-1][k][1]+a[t[i][j-1]]+1ll*x*t[i][j-1];
				f[j][k][1]=f[j-1][k][0]+a[t[i][j-1]]-1ll*x*t[i][j-1];
				if(k)
				{
					f[j][k][0]=min(f[j][k][0],f[j-1][k-1][0]);
					f[j][k][1]=min(f[j][k][1],f[j-1][k-1][1]);
				}
			}
		for(int j=0;j<=cnt;j++)
			for(int k=0;k<=t[i].size();k++)
				if(j+k<=m)
					g[i][j+k]=min(g[i][j+k],g[i-1][j]+f[t[i].size()][k][0]);
		cnt+=t[i].size();
	}
	ll ans=1e18;
	for(int i=0;i<=m;i++)
		ans=min(ans,g[d][i]);
	if(ans>9e17)
	{
		printf("Impossible");
		return 0;
	}
	printf("%lld",ans);
	return 0;
}