Description

    JOI君有N个装在手机上的挂饰,编号为1...N。 JOI君可以将其中的一些装在手机上。
    JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。
    此外,每个挂件有一个安装时会获得的喜悦值,用一个整数来表示。如果JOI君很讨厌某个挂饰,那么这个挂饰的喜悦值就是一个负数。
    JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰,而且一个都不挂也是可以的。

Input

    第一行一个整数N,代表挂饰的个数。
    接下来N行,第i行(1<=i<=N)有两个空格分隔的整数Ai和Bi,表示挂饰i有Ai个挂钩,安装后会获得Bi的喜悦值。 

Output

    输出一行一个整数,表示手机上连接的挂饰总和的最大值

Solution

与普通背包不同的地方在于,这里背包的容量是动态的,所以用f[i][j]表示前i件物品中,满足还剩j个挂钩空着的最大愉悦值,就解决了背包容量未知的问题,然后状态转移方程的推导与01背包相似,如果不取第i个,最优解就是f[i-1][j],如果取,f[i-1][max(j-a[i],0)+1]+b[i]。因为如果不取这个挂饰,挂钩数就只剩下j-a[i]+1个,但这个表达式的值有可能是一个负数,没有意义,所以要取最差的情况,即舍弃所有挂饰,只剩手机上原来的那个挂钩,也就是1个挂钩。

但是有些时候,j-a[i]+1为负数也可能有意义。因为挂钩的位置没有要求,只要后来的挂钩能把j补成非负数就是合法的,但如果去考虑这个,动规的循环变量就不确定,所以要把挂饰按能提供的挂钩数量从大到小排序,就能避免这种情况。

(参考:http://www.cnblogs.com/2014nhc/p/6231288.html)

Code

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[][]; struct rec
{
int a,b;
}x[]; int cmp(const rec&x1,const rec&x2)
{
return x1.a>x2.a;
} int max(int a,int b)
{
return a>b?a:b;
} int main()
{
int n;
scanf("%d",&n);
for (int i=; i<=n; i++)
scanf("%d%d",&x[i].a,&x[i].b);
sort(x+,x+n+,cmp);
memset(f,-,sizeof(f));
f[][]=;
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
f[i][j]=max(f[i-][j],f[i-][max(j-x[i].a,)+]+x[i].b);
int ans=;
for (int i=; i<=n; i++)
ans=max(ans,f[n][i]);
printf("%d",ans);
return ;
}

Source

http://www.lydsy.com/JudgeOnline/problem.php?id=4247

05-01 23:40