Luogu P4241 采摘毒瘤 题解

· · 题解

特判全部装下的情况。

枚举装不下的最小的物品，则必须装体积小于它的所有物品，其它物品可以随意装，只需要满足最后使枚举的这个物品装不下。

设 \operatorname{dp}_j 表示只装入体积不小于当前枚举的物品，使用的体积为 j 的方案数。方案数不能使用二进制分组优化，单调队列优化多重背包可以做到 O(nm)。

将物品按体积从大到小排序，装其它物品的方案可以通过对一段前缀做多重背包得到，答案容易统计。时间复杂度 O(nm)。

注意做多重背包时需要提前将当前枚举的物品数量减一，因为装不下意味着该物品还有剩余。

关于单调队列优化多重背包

对于体积为 c 的物品，暴力的多重背包转移是枚举该物品放 k 个，从所有可能的 k 转移。因为 j \bmod c 只有 c 种可能，枚举不同的余数 r，将 j 表示为 j = pc + r，此时可能转移的 p 构成一段左右端点递增的区间，可以用单调队列维护。

#include<iostream>
#include<algorithm>

using namespace std;

const int mod=19260817;

int n,m;
struct node{
    int x,c;
    friend inline bool operator<(const node &x,const node &y){
        return x.c>y.c;
    }
}a[505];
int f[505];

int q[100005];
int dp[2][100005];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i].x>>a[i].c;
    sort(a+1,a+n+1);
    for(int i=n;i;--i)
        f[i]=f[i+1]+a[i].x*a[i].c;
    if(f[1]<=m){
        cout<<1<<endl;
        return 0;
    }
    int ans=0;
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int r=0;r<a[i].c;++r){
            int ql=1,qr=0,s=0;
            for(int j=0;j*a[i].c+r<=m;++j){
                while(ql<=qr&&j-q[ql]>=a[i].x)
                    s=(s-dp[(i-1)&1][q[ql++]*a[i].c+r]+mod)%mod;
                s=(s+dp[(i-1)&1][j*a[i].c+r])%mod;
                q[++qr]=j;
                dp[i&1][j*a[i].c+r]=s;
            }
        }
        for(int j=max(m-f[i+1]-a[i].c+1,0);j<=m-f[i+1];++j)
            ans=(ans+dp[i&1][j])%mod;
        for(int r=0;r<a[i].c;++r){
            int ql=1,qr=0,s=0;
            for(int j=0;j*a[i].c+r<=m;++j){
                while(ql<=qr&&j-q[ql]>a[i].x)
                    s=(s-dp[(i-1)&1][q[ql++]*a[i].c+r]+mod)%mod;
                s=(s+dp[(i-1)&1][j*a[i].c+r])%mod;
                q[++qr]=j;
                dp[i&1][j*a[i].c+r]=s;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}