首页 > 代码库 > HUD 3466

HUD 3466

2024-11-01 20:16:39   209人阅读

题意就不解释了，要拥有足够的钱才能买对应价值的物品；这里应该按ss-cc排序  而不是按ss排序！
因为for(j=m;j>=q[i].ss;j--)
{
dp[j]=max1(dp[j],dp[j-q[i].cc]+q[i].vv);
}
        当j最小时可以写成  dp[j]=max1(dp[j],dp[q[i].ss-q[i].cc]+q[i].vv);  !!!!!!!q[i].ss-q[i].cc  每次都会跑到这里！！！！
剩下的就是简单的01背包  不解释
#include<iostream>
#include<string.h>
using namespace std;
int dp[5010];
struct node{
	int ss,vv,cc;
}q[5010];
int max1(int a,int b)
{
	if(a>b)
	return a;
	return b;
	
}
int cmp(node a,node b)
{
	return (a.ss-a.cc)<(b.ss-b.cc);
}
int main()
{
	int i,j,n,m,k;
	int c,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
	memset(dp,0,sizeof(dp));
	memset(q,0,sizeof(q));
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d",&q[i].cc,&q[i].ss,&q[i].vv);
	}
	sort(q,q+n,cmp);
	for(i=0;i<n;i++)
	{
		for(j=m;j>=q[i].ss;j--)
		{
			dp[j]=max1(dp[j],dp[j-q[i].cc]+q[i].vv);
		}
	}
	printf("%d\n",dp[m]);
	
}return 0;
}

HUD 3466


联系
我们