洛谷P4138 [JOISC2014]挂饰 题解

description：

JOI君有N个装在手机上的挂饰，编号为1…N。 JOI君可以将其中的一些装在手机上。

JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。

此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。

JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

solution：

$设f\left[i\right]\left[j\right]表示前i个挂钩，有j个挂饰时的最大喜悦值$设f[i][j]表示前i个挂钩，有j个挂饰时的最大喜悦值

$那么f\left[i\right]\left[j\right]=max\left(f\right[i-1\left]\right[j],f[i-1\left]\right[max(j-d[i].a,0)+1]+d[i\left].b\right);$那么f[i][j]=max(f[i−1][j],f[i−1][max(j−d[i].a,0)+1]+d[i].b);

显然在普通背包的基础上考虑负值带来的影响就行了

还有就是注意要排序，因为如果先算钩子少的极有可能多次挂上没有意义

code:

#include<cstdio>
#include<algorithm>
#define minx -1000000000
using namespace std;
struct ben
{
	int a,b;
}d[2005];
int cmp(const ben &x,const ben &y)
{
	return x.a>y.a;
}
int f[2005][2005];
int main()
{
	int n;
	scanf("%d",&n);
	int m=0;
	for(int i=0;i<=n;i++)
	{
		f[0][i]=f[i][n+1]=minx;
	}
	f[0][1]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&d[i].a,&d[i].b);
	}
	sort(d+1,d+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			f[i][j]=max(f[i-1][j],f[i-1][max(j-d[i].a,0)+1]+d[i].b);
		}
	}
	int ans=-2000000000;
	for(int i=0;i<=n;i++)
	{
		ans=max(ans,f[n][i]);
	}
	printf("%d\n",ans);
	return 0;
}