description:

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

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

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

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

solution:

f [ i ] [ j ] i j 设f[i][j]表示前i个挂钩,有j个挂饰时的最大喜悦值 f[i][j]ij

f [ i ] [ j ] = m a x ( f [ i 1 ] [ j ] , f [ i 1 ] [ m a x ( j d [ i ] . a , 0 ) + 1 ] + d [ i ] . b ) ; 那么f[i][j]=max(f[i-1][j],f[i-1][max(j-d[i].a,0)+1]+d[i].b); f[i][j]=max(f[i1][j],f[i1][max(jd[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;
}