经典排序背包——cf1203F

逃离我推掉我的手 2023-10-11 09:09 82阅读 0赞

先把收益为正数的处理掉：策略是挨个扫，扫n遍，碰到能买的就买，然后可以得到一个更新后的r

剩下的就看做是一个背包模型：物品(a,b)表示当背包体积>a时才能装下体积为b的该物品，问最多装几个

无序枚举所有物品显然错误，要选择先买哪个更优

对于两个物品(ai,bi),(aj,bj)，有两种顺序

先买i，则至少需要max(ai,aj+bi)的体积

先买j，则至少需要max(aj,ai+bj)的体积

因为每买一件物品，剩余体积必定下降，为了达到某种状态，我们必须选择那种需要体积小的顺序

那么比较 aj+bi和ai+bj即可，转化成比较aj-bj和ai-bi，对这个差值降序排序

/*
    排序背包，本题要考虑两个物品(a1,b1),(a2,b2)谁先买
        先买第一种最少要max(a1,a2-b1),先买第二件最少要max(a2,a1-b2) 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define N 30005
    int dp[105][N<<1],n,r;
    struct Node{
        int a,b;
    }c[105],d[105];
    int cmp(Node a,Node b){
        return a.a+a.b>b.a+b.b;}
    int cnt1,cnt2,vis[N];
    int main(){
        cin>>n>>r;
        for(int i=1;i<=n;i++){
            int a,b;cin>>a>>b;
            if(b>0){
                cnt1++;
                c[cnt1].a=a,c[cnt1].b=b;
            }
            else {
                cnt2++;
                d[cnt2].a=a,d[cnt2].b=b;
            }
        }
        
        int tot=0;
        for(int i=1;i<=cnt1;i++)
            for(int j=1;j<=cnt1;j++)
                if(!vis[j] && r>=c[j].a){
                    r+=c[j].b;
                    vis[j]=1;
                    tot++;
                    break;
                }
        
        sort(d+1,d+1+cnt2,cmp);
        memset(dp,-0x3f,sizeof dp);
        dp[0][r]=tot;
        for(int i=1;i<=cnt2;i++)
            for(int j=0;j<=r;j++){
                if(dp[i-1][j]>=0)//不选第i件 
                    dp[i][j]=dp[i-1][j];
                if(j-d[i].b>=d[i].a && dp[i-1][j-d[i].b]>=0)//选第i件 
                    dp[i][j]=max(dp[i][j],dp[i-1][j-d[i].b]+1);
            }
        
    
        int ans=0;
        for(int j=r;j>=0;j--)
            if(dp[cnt2][j]>=0)ans=max(ans,dp[cnt2][j]);
        cout<<ans<<endl; 
    }

转载于:https://www.cnblogs.com/zsben991126/p/11515349.html