bzoj4247 挂饰

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)

正解：背包$dp$。

设$f[i][j]$表示前$i$个挂饰，当前有$j$个挂钩的最大值。那么直接按照背包的转移做，把不合法方案用$-inf$堵住就行了。

注意要先从大到小排序，因为不能先做没有挂钩的挂饰。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define inf (1LL<<50)
 6 
 7 using namespace std;
 8 
 9 struct data{ int a,b; }p[2010];
10 
11 ll f[2010][2010],ans;
12 int n;
13 
14 il int gi(){
15   RG int x=0,q=1; RG char ch=getchar();
16   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
17   if (ch=='-') q=-1,ch=getchar();
18   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
19   return q*x;
20 }
21 
22 il int cmp(const data &x,const data &y){ return x.a>y.a; }
23 
24 int main(){
25 #ifndef ONLINE_JUDGE
26   freopen("ornament.in","r",stdin);
27   freopen("ornament.out","w",stdout);
28 #endif
29   n=gi();
30   for (RG int i=1;i<=n;++i) p[i].a=gi(),p[i].b=gi();
31   for (RG int i=0;i<=n;++i)
32     for (RG int j=0;j<=n;++j) f[i][j]=-inf;
33   sort(p+1,p+n+1,cmp),f[0][0]=0;
34   for (RG int i=1;i<=n;++i){
35     for (RG int j=0,k;j<=n;++j){
36       if (f[i-1][j]==-inf) continue;
37       f[i][j]=max(f[i][j],f[i-1][j]),k=min(n,j+p[i].a-1);
38       if (k>=0) f[i][k]=max(f[i][k],f[i-1][j]+1LL*p[i].b);
39     }
40     f[i][p[i].a]=max(f[i][p[i].a],1LL*p[i].b);
41   }
42   for (RG int i=0;i<=n;++i) ans=max(ans,f[n][i]);
43   printf("%lld
",ans); return 0;
44 }