题解 P4138 【[JOISC2014]挂饰】

ShineEternal

2019-10-03 20:45:19

Solution

[如有LaTeX显示问题可查看这里](https://blog.csdn.net/kkkksc03/article/details/102016431) ## description: JOI君有N个装在手机上的挂饰,编号为1...N。 JOI君可以将其中的一些装在手机上。 JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。 此外,每个挂件有一个安装时会获得的喜悦值,用一个整数来表示。如果JOI君很讨厌某个挂饰,那么这个挂饰的喜悦值就是一个负数。 JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰,而且一个都不挂也是可以的。 ## solution: $设f[i][j]表示前i个挂钩,有j个挂饰时的最大喜悦值$ $那么f[i][j]=max(f[i-1][j],f[i-1][max(j-d[i].a,0)+1]+d[i].b);$ 显然在普通背包的基础上考虑负值带来的影响就行了 还有就是注意要排序,因为如果先算钩子少的极有可能多次挂上没有意义 ## code: ```cpp #include<cstdio> #include<algorithm> #define minx -1000000000 using namespace std; struct ben { int a,b; }d[2005]; int cmp(const ben &x,const ben &y) { return x.a>y.a; } int f[2005][2005]; int main() { int n; scanf("%d",&n); int m=0; for(int i=0;i<=n;i++) { f[0][i]=f[i][n+1]=minx; } f[0][1]=0; for(int i=1;i<=n;i++) { scanf("%d%d",&d[i].a,&d[i].b); } sort(d+1,d+n+1,cmp); 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-d[i].a,0)+1]+d[i].b); } } int ans=-2000000000; for(int i=0;i<=n;i++) { ans=max(ans,f[n][i]); } printf("%d\n",ans); return 0; } ```