自动搬运

查看原文

来自洛谷，原作者为

	zzy_123 **

搬运于2025-08-24 21:33:45，当前版本为作者最后更新于2018-10-08 20:44:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

//本题可以看做一个模板题吧(我认为),因为许多类似题的方法可以按照本题来。如(P2340) 都需要按照题意转化为背包问题。 这里也是如此，先把小明的喜爱度与钱转化为背包来储存小红喜爱度的最大值。 代码：

#include<bits/stdc++.h>
using namespace std;
int f[610][600],n,m,j,k,l;//f数组代表花费n元与小明喜爱程度为m使小红获得喜爱度的最大值
//也可以不压缩(已经压缩了一维)，应该都会01背包的压缩吧。
//因为小明的喜爱度可以为负数，所以根据数据把数组开大一倍。（本应该开1000以上的但是忘记开到那么大就AC了。。。只把第2维开到了600）。假设数组的300位为0,299为-1,301为1，就可以把负数的情况弄到数组里面去了。
struct zzy
{
	int ci,xi,yi;
}sum[1000];
void cot()
{
	int a,b,c,d,e;
	for(a=1;a<=m;a++)
	{
		for(b=0;b<=10;b++)
		cout<<f[a][b]<<" ";cout<<endl;
	}cout<<endl;
}
int main()
{
	//f[n][m]=max f[n-j][m-k]+sum[t].yi,f[n][m]; 
    //状态转移方程
	int a,b,c,d,e;
	cin>>n>>m;
	for(a=1;a<=n;a++)
	cin>>sum[a].ci>>sum[a].xi>>sum[a].yi;
	for(a=1;a<=n;a++)
	{
		for(b=m;b>=sum[a].ci;b--)
		{
        //根据这道菜小明的喜爱度，因为把数组压缩了一维，所以要倒退，所以正数与负数的退发不一样。
			if(sum[a].xi>0)
			{
				for(c=600;c-sum[a].xi>=0;c--)
				{
                //因为在考虑时有许多情况是不可能到达地，所以不能转移，不然会爆错，也就是考虑初始边界情况。
					if(f[b-sum[a].ci][c-sum[a].xi]==0&&c!=sum[a].xi+300)continue;
					else
					f[b][c]=max(f[b][c],f[b-sum[a].ci][c-sum[a].xi]+sum[a].yi);
				}
			}
			else
			{
				for(c=0;c<=600+sum[a].xi;c++)
				{
					if(f[b-sum[a].ci][c-sum[a].xi]==0&&300-c!=abs(sum[a].xi))continue;
					else
					{
						f[b][c]=max(f[b][c],f[b-sum[a].ci][c-sum[a].xi]+sum[a].yi);
					}
				}
			}
		}
	}c=0;
	for(a=1;a<=m;a++)
	{
		for(b=300;b<=600;b++)c=max(c,f[a][b]);
	}//取最后小明喜爱度大于0的值。
	if(c>=0)cout<<c;
	else cout<<-1;
}