题解 P4241 【采摘毒瘤】
Salamander
·
·
题解
大意：一些物品，每个有数量和大小，给你一个有总容量限制的背包，要求选一些物品使得剩余的物品都放不进去，求方案数。
我们先考虑如何暴力。如果没有限制条件，那么本题就是一个裸的多重背包计数。
所以我们可以枚举剩下的物品中最小的是哪一个，把比他小的先放进去，然后对它和比它大的做多重背包。
记当前枚举的最小物品为i，V_i为大小，k_i为数量，当前比i小的物品总大小为sum，背包容量为m，dp[j]表示物品总大小为j时的方案总数。
那么当前的方案总数为\displaystyle\sum_{j=m-sum-V_i+1}^{m-sum}dp[j]，因为当前留下的背包空间最大为m-sum，我们不能让V_i有能放进去的地方，所以空间最小为m-sum-V_i+1。同时，我们必须留下至少一个物品i不放进去，所以在做多重背包的时候k_i要减一。
~
$30pts$: 枚举剩下的最小物品，然后多重背包。
在我们的暴力中，每次都进行了一次$i$到$n$的多重背包，这样浪费了很多信息。
所以我们可以从大到小枚举所剩的物品中最小的是哪一个，这样就可以利用上上一轮的$dp$数组，只需要把当前物品加入到$dp$数组中即可，不需要重新$dp$。
$50pts$: 有20分的数据是01背包，所以利用上一次的信息可以将复杂度降至01背包复杂度$O(nm)$。
$100pts$: 可以在更新背包的时候按模$V_i$余数分组，用队列的思想优化多重背包至$O(nm)$即可通过此题(详见徐持衡的国家集训队论文，不过应该差不多已经烂大街了...)。
代码很短：
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)
template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
T f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
x*=f;
}
const int N=510,maxn=1000010,mod=19260817;
struct Thing{
int k,d;
bool operator<(const Thing &x)const{return d<x.d;}
}a[N];
int n,m,ans,tot,dp[2][maxn],cur;
inline int M(int x){return x>=mod?x-mod:x;}
void Insert(int k,int w){
int sum,H;
For(d,0,w-1){
H=sum=0;
For(j,0,(m-d)/w){
sum=M(sum+dp[cur^1][j*w+d]);
if(H<j-k)sum=M(sum-dp[cur^1][(H++)*w+d]+mod);
dp[cur][j*w+d]=sum;
}
}
}
int main(){
read(n);read(m);
For(i,1,n) read(a[i].k),read(a[i].d),tot+=a[i].k*a[i].d;
if(tot<=m)return puts("1"),0;
sort(a+1,a+n+1);
dp[0][0]=1;
Rep(i,n,1){
tot-=a[i].k*a[i].d;
cur^=1;
Insert(a[i].k-1,a[i].d);
For(j,Max(m-tot-a[i].d+1,0),m-tot) ans=M(ans+dp[cur][j]);
Insert(a[i].k,a[i].d);
}
printf("%d\n",ans);
return 0;
}
```