题解 P4138 【挂饰】

· · 题解

莫名其妙找了这道题，然后莫名其妙的做了好几天。

想看题解发现是个dfs记忆剪枝，不是动规于是自己苦打终于打出来了

其实这是一道很好的背包题

费用是一维————————挂钩

但是我没有敢压缩状态，所以开了二维数组

f[i][j]表示前i件物品在有j个挂钩的情况下的最大价值

然后状态转移为f[i][j]=max(f[i-1][j],f[i-1][j-w[i]+1]+v[i])

这是错的

因为j-w[i]+1可能是个负数，没有意义，这时候就要考虑这物品直接挂在手机上即j=1，也就需要我们把j-w[i]和0取最大值保证有意义

所以正解方程为f[i][j]=max(f[i-1][j],f[i-1][max(j-w[i].a,0)+1]+w[i].b);//这里的a是钩子，b是价值

为什么我用结构体呢？

并不是我闲的*疼，而是我们要进行一个排序让钩子多的在前面先计算，这个因为把钩子少的先计算很有可能多次挂在手机上没有意义

然后赋初值

我们应该把不可能的情况赋成极小值即

for(int i=0;i<=n;i++) f[0][i]=MAXN,f[i][n+1]=MAXN;

然后f[0][1]=0这是初始状态

下面贴AC代码

#include<bits/stdc++.h>//注意万能头比赛不能用
using namespace std;
const int MAXN=-1000000000;
int f[3010][3010];//蒙的数据范围
struct wu{
    int a,b;
}w[3010];
bool cmp(wu i,wu j){
    return i.a>j.a;
}
int ans=-2147483647;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i].a,&w[i].b);
    sort(w+1,w+1+n,cmp);
    for(int i=0;i<=n;i++) f[0][i]=MAXN,f[i][n+1]=MAXN;
    f[0][1]=0;
    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-w[i].a,0)+1]+w[i].b);
        }
    }
    for(int i=0;i<=n;i++) ans=max(ans,f[n][i]);//每个钩子都有可能
    cout<<ans;
    return 0;
}