P4138 [JOISC2014]挂饰

◦          N个装在手机上的挂饰。挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。此外,每个挂件有一个安装时会获得的喜悦值,用一个整数来表示,可能为负。

◦          想要选出一些挂饰挂在一起,最大化所有挂饰的喜悦值之和。

◦          1<=N<=2000
           0<=Ai<=N(1<=i<=N)表示挂勾的数量
           -10^6<=Bi<=10^6(1<=i<=N)表示喜悦值。

>Solution

◦          首先贪心的想,如果最终选出的一组挂饰,肯定是从上到下先挂所含挂钩多的。所以先按照挂钩数量从大到小排序。

Why??

(1)0       100   挂钩数  喜悦值

(2)1  100

乱序ans为100

◦          然后设dp[i][j]前i个挂饰,剩余j个挂钩的最大喜悦值是多少即可。

◦          转移枚举下一个挂饰是否挂。

◦          挂,挂钩数更新就 j - 1 + a[i+1],对应的修改喜悦值;不挂,挂钩数就直接转移过来

但是这个值可能是个负数啊,dp[i][0]就不能转移了啊

◦        转移方程: dp[i][j]=max(dp[i-1][j],dp[i-1][max(j-a[i],0) +1]+v[i])

注意此处为什么是P4138 [JOISC2014]挂饰-LMLPHP这个+1放在外面呢???

假设我们挂第 i 个挂饰,那么挂之前有 i-1 个挂饰,有 x 个挂饰,那么 x-1+a[i]=j,

因为挂上第 i 个挂饰要消耗一个挂钩,然后你会得到第 i 个挂饰的挂钩

所以 x = j - a[i] + 1

j-a[i]有可能是负数,一旦是负数,那肯定就不存在此情况,就相当于你把之前的挂饰全从手机上卸下来,然而手机默认自己就有一个挂钩,所以+1放到外面

◦          注意dp[i][0]不能转移。

状态设计充分描述尽量简洁,什么影响问题就把什么记下来

PS:奉劝各位 f 数组一定要初始化最小值!!!

        memset(f,-0x3f3f3f3f,sizeof(f))

       (不过你初始化的这个值并不等于-0x3f3f3f3f,是一个绝对值较大的负数

       (这个T我写的-0x3f没有事,因为memset是用最后两位来填充的数组

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue> using namespace std; inline int read()
{
int ans=;
char last=' ',ch=getchar();
while(ch<''||ch>'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
} const int maxn=,minn=-;
int n,ans=;
int f[maxn][maxn];
struct node
{
int a,b;
}gou[maxn]; bool cmp(node x,node y)
{
if(x.a==y.a) return x.b >y.b ;
return x.a >y.a ;
} int main()
{
n=read();
for(int i=;i<=n;i++)
gou[i].a =read(),gou[i].b=read();
sort(gou+,gou+n+,cmp);
memset(f,-0x3f,sizeof(f)); f[][]=; for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j]=max(f[i-][j],f[i-][max(j-gou[i].a,)+]+gou[i].b ); for(int i=;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%d",ans);
return ;
}
05-11 22:15