自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 22:20:44，当前版本为作者最后更新于2020-04-01 14:39:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

update on 7.7:出题人谢罪，修改了一些锅，原来的数据太水了，希望管理员重新通过一下

此题是一道简单的背包$dp$。

先特判一遍，如果所有 $x_{i}$ 的和小于等于 $m$ ，那么就是一个贪心（因为父母会偷掉一道题），否则的话就不用管父母（因为不能全部出完数据，让父母偷掉一道没有出数据的题就可以了）。

然后用 $dp_{i,j}$ 表示用 $i$ 时间，使用 $j$ 次翻倍后可以得到的最大毒瘤值。

对于每一对 $a_{i}$ 和 $x_{i}$ ，都有 $dp_{i,j} = \max(dp_{i,j} , dp_{i-x_i , j} + a_i , dp_{i-x_i , j-1} + 2 \times a_i )$

同时，老师可能没有用完，所以取 $dp$ 数组中的最大值即可。

c++代码如下：

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

int n,m,k,f[1005][105];
int a[1005],x[1005],sum,ans=0;

int cmp(int a,int b)
{
	return a>b;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&x[i]),sum+=x[i];
	if (sum<=m)//特判
	{
		int ans=0;
		sort(a+1,a+1+n,cmp);
		for (int i=1;i<=k;i++)
			ans+=a[i]*2;
		for (int i=k+1;i<n;i++)
			ans+=a[i];
		cout<<ans;
		return 0;
	}
	for (int e=1;e<=n;e++)
		for (int i=m;i>=x[e];i--)
		{
			for (int j=min(k,e);j>=1;j--)//注意，这里要倒叙枚举
				f[i][j]=max(f[i][j],max(f[i-x[e]][j]+a[e],f[i-x[e]][j-1]+a[e]*2)),ans=max(ans,f[i][j]);
			f[i][0]=max(f[i][0],f[i-x[e]][0]+a[e]);ans=max(ans,f[i][0]);
		}
	cout<<ans;
	return 0;
}