[bzoj4247][DP]挂饰

2023-10-16 03:58

文章标签 dp 挂饰 bzoj4247

本文主要是介绍[bzoj4247][DP]挂饰，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

5

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然后发现是N^3的转移，或许是我的转移太丑了？机房有人表示一维可做
那就写二维吧
设f[i][j]表示前i个物品，剩下j个钩子的最大喜悦值
首先你肯定要按钩子数量排序嘛，因为N^2转移里肯定要求钩子越多越好啦
然后，钩子那一维可以只开N，因为只有N个物品其他也装不下。
转移可以看代码特别好懂的

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int f[2100][2100],n;
bool v[2100][2100];
struct node
{int a,b;
}A[2100];
bool cmp(node n1,node n2){return n1.a>n2.a;}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&A[i].a,&A[i].b);sort(A+1,A+1+n,cmp);int ans=0;memset(v,false,sizeof(v));v[0][1]=true;memset(f,-63,sizeof(f));f[0][1]=0;for(int i=1;i<=n;i++)for(int j=0;j<=n;j++){if(v[i-1][j] && j!=0)f[i][min(n,j-1+A[i].a)]=max(f[i][min(n,j-1+A[i].a)],f[i-1][j]+A[i].b),v[i][min(n,j-1+A[i].a)]=true;f[i][j]=max(f[i][j],f[i-1][j]);v[i][j]|=v[i-1][j];}for(int i=0;i<=n;i++)if(v[n][i])ans=max(ans,f[n][i]);printf("%d\n",ans);return 0;
}