摘要:完全背包后容斥

[HAOI2008]硬币购物

题面

题目分析

假设没有每次使用货币的限制,那么这题就是一个完全背包求方案数.

现在考虑只有一种货币,加上使用这种货币的限制,答案就为dp[n]-dp[n-c*(d+1)],即不能计入答案的是使用了超过d枚货币的情况,我们把d+1枚货币的价值取出来,剩下的部分的用完全背包算出的方案数就是不需要的答案,减去即可.

但是现在有4种货币,容斥一下即可,先减去每种货币不应该计入答案的,然后加上两种货币不应该计入答案的,减去三种货币不应该计入的,加上四种货币不应该计入的.

代码

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
51
52
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "cstdlib"
#include "iomanip"
#include "algorithm"
#include "time.h"
#include "set"
#include "queue"
#include "deque"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=100010;
lxl n,s,ans;
lxl c[4],d[4],dp[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
int main(void)
{
c[0]=read(),c[1]=read(),c[2]=read(),c[3]=read(),n=read();
dp[0]=1;
for(R int i(0);i<4;++i)
for(R int j(c[i]);j<=maxn;++j)
dp[j]+=dp[j-c[i]];
while(n--)
{
ans=0;
d[0]=read(),d[1]=read(),d[2]=read(),d[3]=read(),s=read();
for(R int i(0);i<16;++i)
{
lxl tmp=s,which=0;
for(R int j(0);j<4;++j)if((i>>j)&1)which^=1,tmp-=(c[j]*(d[j]+1));
if(tmp<0)continue;
if(!which)ans+=dp[tmp];else ans-=dp[tmp];
}
printf("%lld\n",ans);
}
return 0;
}