BZOJ 4247 挂饰

题目大意

JOI君有N个装在手机上的挂饰，编号为1...N。 JOI君可以将其中的一些装在手机上。

JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。

此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。

JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

这道题一看到题面就基本看出来了——是$O(n^2)$DP.但是在比赛的时候我写挂了QwQ究竟是为什么呢？

我们设f[i][j]表示前i个挂件挂在手机上还剩下j个挂钩（严格定义）的最大愉悦值。我们可以想到，需要先进行一次排序，确保挂钩数量比较大的先往上挂，这样的话就可以保证不会出现挂钩没地方挂的尴尬场面。之后就是递推方程式。

本来是有一个Universal的通用方程的，但是这样的话如果我们走的是严格就会导致挂钩数量一维可能会非常大，MLE不说TLE是一定的QwQ

所以我们考虑其他方案，比如下面的一维递推。

我们一共有几种可能的更新方案。

• 挂钩数量等于1，愉悦值$\gt 0$
• 挂钩数量等于0，愉悦值$\gt 0$
• 挂钩数量大于1

如果挂钩数量等于一愉悦值$\gt 0$，直接将此时的所有的方案都加上这个愉悦度，此时没有任何影响。

如果挂钩数量等于0，此时钩子数量从1枚举到n，尝试更新这些方案。

如果挂钩数量大于1，此时算出挂完钩子之后剩余的钩子数量为j+a[i]-1，之后我们从f[k-a[i]+1]向回推就好了。

钩子数量最高n,如果钩子数量高于n的话直接自动修复回n就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxN=2010;
int n;
long long f[maxN],ans;
struct item
{
    int a,b;
}x[maxN];
bool cmp(item tx,item ty) {return tx.a>ty.a;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&x[i].a,&x[i].b);
    sort(x+1,x+n+1,cmp);
    memset(f,0x80,sizeof f);
    f[1]=0;
    for(int i=1;i<=n;++i)
    {
        if(x[i].a>1) for(int j=n+x[i].a-1;j>=x[i].a;j--) f[min(j,n)]=max(f[min(j,n)],f[j-x[i].a+1]+x[i].b);
        if(!x[i].a&&x[i].b>0) for(int j=0;j<=n-1;++j) f[j]=max(f[j],f[j+1]+x[i].b);
        if(x[i].a==1&&x[i].b>0) for(int j=0;j<=n;++j) f[j]+=x[i].b;
    }
    for(int i=0;i<=n;++i) ans=max(ans,f[i]);
    printf("%lld",ans);
    return 0;
}