自动搬运

查看原文

来自洛谷，原作者为

	bluewindde d2673e765642345244b4fb8edf1add1cf8425a4b7743f39b020d410d67ce15b0

搬运于2025-08-24 21:58:01，当前版本为作者最后更新于2025-08-19 21:42:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

特判全部装下的情况。

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

设 $\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;
}