题目描述
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
数据规模
di,s<=100000
tot<=1000
题解：
首先，我们不考虑硬币的限制，用动态规划求解背包方案数。然后考虑容斥原理，进行解题。编程上有技巧：使用dfs来减少代码量。
#include<cstdio>
typedef long long ll;
const int maxn = 1e5+10;
int c[4],d[4];
int tot;
int S;
ll f[maxn],ans;
inline void prelude(void) {
f[0]=1;
for(int i = 0;i<4;++i) {
for(int V=c[i];V<maxn;++V) {
f[V]+=f[V-c[i]];
}
}
return;
}
inline void dfs(int pos,int inv,int rem) {
if(rem<0) return;
if(pos==4) {
ans+=inv*f[rem];
return;
}
dfs(pos+1,inv,rem);
dfs(pos+1,-inv,rem-((d[pos]+1)*c[pos]));
}
int main() {
scanf("%d%d%d%d%d",c,c+1,c+2,c+3,&tot);
prelude();
while(tot--) {
scanf("%d%d%d%d%d",d,d+1,d+2,d+3,&S);
ans = 0;
dfs(0,1,S);
printf("%lld
",ans);
}
return 0;
}