P4138 [JOISC2014] 挂饰 题解
Harry_Hedwig
·
2021-06-19 11:02:09
·
题解
0x00 思路
先看题。
JOI君有 N 个装在手机上的挂饰，编号为 1 ~ N 。 JOI君可以将其中的一些装在手机上。JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 1 个 。此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。JOI君想要最大化 所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的 。
对于每一个挂件，我可以选择挂或不挂，那么由于每个挂件只有 1 个，所以这是一个 01 背包。
可是这又与 01 背包有一点区别：每一个物品多了一个属性：挂钩数,因此为了适应这个多出来的属性，我们决定把它变成背包容量。
接着因为我们认为，挂钩越多越有用（因为能挂的挂件越多欢喜值越大（都是整数的情况下）），所以我们按照挂钩的数量从大到小排序。
0x01 定义状态
对于 d[i][j] ，我们定义：挂完或选择不挂后 第 i 个挂件后还剩余 j 个空挂钩所得的最大喜悦值。
0x02 状态转移方程
那么很容易，我们可以发现有 2 种情况：
不选用它
这个状态很简单，由于是 01 背包，所以 d[i][j]=d[i-1][j] 。
选用它
这个状态有 2 种情况。
一种是 j \geq A_i : 那么此时的 d[i][j] 就等于 d[i-1][j-A_i+1]+B_i (这个挂件需要 1 个挂钩)。
另一种是 j<A_i : 由于我们挂了这个挂件，所以必须得有一个挂钩来挂这个挂件，而此时 j-A_i+1<0 ，所以我们强行 认为它是 1 。
所以状态转移方程就是 d[i][j]=\max(d[i-1][j],d[i-1][\max(j-A_i,0)+1]+B_i) 。
0x03 注意优化！
为什么呢？
由于 $A_i$ 可能为 $0$ ，而 $j>0$，所以可能会用到 $d[i-1][j+1]$ 的值，而用一维数组的话 $j+1$ 已经被赋成 $d[i][j+1]$ 了，所以只能用 $2$ 行。
# code
```c
#include<bits/stdc++.h>
using namespace std;
int d[2005][2005];
struct gs
{
int gg,hxz;
}a[2005];
bool cmp(gs b,gs c)
{
return b.gg>c.gg;
}
int main()
{
int n,m,i,j,ans=0;
scanf("%d",&n);
memset(d,128,sizeof(d));
d[0][1]=0;
for(i=1;i<=n;i++)
scanf("%d %d",&a[i].gg,&a[i].hxz);
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
for(j=0;j<=n;j++)
d[i][j]=max(d[i-1][j],d[i-1][max(j-a[i].gg,0)+1]+a[i].hxz),ans=max(ans,d[i][j]);
printf("%d",ans);
return 0;
}
```