Steven_MengのBlog

有时候,我们在做背包问题时会遇到如下情况,给你一大堆询问,要你求出满足某种限制,填满背包的方法数。

先来一道例题:

例题1:

P1450 [HAOI2008]硬币购物

乍眼一看似乎是一个裸的完全背包,但是注意到询问组数较多,每次跑一遍完全背包绝对会炸掉,考虑预处理出不带限制的方法数,然后用容斥除去不满足限制的方法

预处理,用题目的四种硬币凑出$x$元的钱共有$f(x)$种方法:

1
2
3
4
5
6
7
8
inline void Init(){
dp[0]=1;
for (register int i=1;i<=4;++i){
for (register int j=c[i];j<MAXN;++j){
dp[j]+=dp[j-c[i]];
}
}
}

简单容斥:

1
2
3
4
5
6
7
8
9
10
for (register int i=0;i<16;++i){
int f=1,sum=0;
for (register int j=1;j<=4;++j){
if (i&(1<<(j-1))) {
f*=-1;
sum+=(d[j]+1)*c[j];
}
}
if (s-sum>=0) ans+=f*dp[s-sum];
}

为什么是$(d[j]+1)*c[j]$,不妨考虑先用$d[j]+1$个硬币$j$,这样肯定是不符合的,所以要减去。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int c[5],d[5];
int dp[MAXN];
inline void Init(){
dp[0]=1;
for (register int i=1;i<=4;++i){
for (register int j=c[i];j<MAXN;++j){
dp[j]+=dp[j-c[i]];
}
}
}
#undef int
int main(){
#define int long long
for (register int i=1;i<=4;++i) c[i]=read();
Init();
int tot=read();
while (tot--){
for (register int i=1;i<=4;++i) d[i]=read();
int s=read();
int ans=0;
for (register int i=0;i<16;++i){
int f=1,sum=0;
for (register int j=1;j<=4;++j){
if (i&(1<<(j-1))) {
f*=-1;
sum+=(d[j]+1)*c[j];
}
}
if (s-sum>=0) ans+=f*dp[s-sum];
}
printf("%lld\n",ans);
}
}

例题2:

P4141 消失之物

跟上面一样,先预处理出来没有任何限制的方法数,注意是01背包:

1
2
3
4
5
6
f[0]=1;
for (register int i=1;i<=n;++i){
for (register int j=m;j>=w[i];--j){
f[j]=(f[j]+f[j-w[i]])%MOD;
}
}

这里的容斥就比较简单:

1
2
3
4
5
6
7
ans[i][0]=1;
for (register int j=1;j<w[i];++j){
ans[i][j]=f[j];
}
for (register int j=w[i];j<=m;++j){
ans[i][j]=(f[j]-ans[i][j-w[i]]+MOD)%MOD;//容斥一下
}

对于$<w[i]$的情况,一定里面合法方案没有$w[i]$这个物品,所以$ans[i][j]=f[j]$

对于$\geq w[i]$的情况,需要进行容斥,$ans[i][j]=f[j]-ans[i][j-w[i]]$,注意到是$ans[i][j-w[i]]$而不是$f[j-w[i]]$,原因是$f[j-w[i]]$的方案里面可能包含$w[i]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define MAXN 2005
#define MOD 10
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
static int w[MAXN],f[MAXN],ans[MAXN][MAXN];
int main(){
int n=read(),m=read();
for (register int i=1;i<=n;++i) w[i]=read();
f[0]=1;
for (register int i=1;i<=n;++i){
for (register int j=m;j>=w[i];--j){
f[j]=(f[j]+f[j-w[i]])%MOD;
}
}
for (register int i=1;i<=n;++i){
ans[i][0]=1;
for (register int j=1;j<w[i];++j){
ans[i][j]=f[j];
}
for (register int j=w[i];j<=m;++j){
ans[i][j]=(f[j]-ans[i][j-w[i]]+MOD)%MOD;//容斥一下
}
}
for (register int i=1;i<=n;++i){
for (register int j=1;j<=m;++j){
putchar(ans[i][j]+'0');
}
puts("");
}
}

 评论