BZOJ 4247: 挂饰题解

Description

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

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

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

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

Input

第一行一个整数N，代表挂饰的个数。

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

Output

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

Sample Input

5
0 4
2 -2
1 -1
0 1
0 3

Sample Output

HINT

将挂饰2直接挂在手机上，然后将挂饰1和挂饰5分别挂在挂饰2的两个挂钩上，可以获得最大喜悦值4-2+3=5。

1<=N<=2000

0<=Ai<=N(1<=i<=N)

-10^6<=Bi<=10^6(1<=i<=N)

题解：我表示这道题是在老师和同学耗尽心思的讲解中才勉强懂了一点却因为输入输出调了十遍RE。。。

不过很开心的是这道题在他人的讲解和我看题解的过程中让我对动归的理解比以前稍微好了一点（虽然还是很菜），希望能有更多提升。

好啦看题目，这道题其实就是背包的容量在不停的变化，用f[i][j]来表示挂完第i个物品后还剩j个挂钩，那么转移方程为f[i][j]=max(f[i-1][j],f[i-1][max(j-a[i],0)+1]+b[i]);

为什么这么写呢？解释一下：首先f[i][j]=f[i-1][j]很好懂就是指现在这个物品不挂，可取得的喜悦值,那么f[i-1][max(j-a[i],0)+1]是什么意思呢，我们先看j-a[i]+1,这是指上一次的挂钩值，那么后面的这个式子意思是把这个饰件挂上的喜悦值+上一次的喜悦值，但是j-a[i]是有可能小于0的，即如果第i个物品挂上去的话这次不可能就j个挂钩，这个时候我们就假设上一次只剩了一个挂钩，这样j个挂钩都是现在第i个物品带来的，即使j-a[i]<0,也可以当做我们把多余j的挂钩给舍去了。为什么我们要假设上一次只剩了一个挂钩呢？因为当前物品如果能挂上去，说明上一次多出的挂钩数一定大于等于1，却不能保证大于1，所以我们至多只能设上次只剩了一个挂钩（只有一是能被确定的），这就是这个式子让我当时最不理解的地方。。。。。

好啦，第二个重点，在做动归前我们需要将a数组排一下序，为何因为我们会发现如果不排序的话我们这次挂上这个饰品，即使j是负数也并不是不合法的，因为挂饰间可以互换位置，只要后面挂饰的挂钩能够把j在最后补成自然数就可以了，那样就会导致动归的循环不确定，没法一步步推，所以要进行排序。

ps:最好别用输入输出流，我的RE好像就错在这，可能是因为输入数据有点大吧。。。

具体程序:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
struct h{
int k,t;
}x[2500];
int cmp(const h&a,const h&b)
{
return a.k>b.k;
}
int max(int a,int b)
{
return (a>b?a:b);
}
int f[2500][2500];
int pop,n,ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d %d",&x[i].k,&x[i].t) ;
//k为挂钩数，t为喜悦值
sort(x+1,x+n+1,cmp);//排序
memset(f,-210000000,sizeof(f));//先预处理为最小值
f[0][1]=0;//手机上原来就有个挂钩所以算作0；
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-x[i].k,0)+1]+x[i].t);
ans=0; 
for (int i=0;i<=n;i++)
ans=max(ans,f[n][i]);//去看看最后的答案
printf("%d",ans);
return 0;
}