【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1042
【题目大意】
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。
某人去商店买东西，去了tot次。每次带di枚ci硬币，
买si的价值的东西。请问每次有多少种付款方法。
【题解】
我们首先预处理出没有限制情况下不同容量的方案数，等价于一般的背包问题
之后对于硬币数量限制问题考虑容斥，
方案数等于无限制方案数-面值为c1的硬币超出限制的方案数-面值为c2的硬币超出限制的方案数-……
+面值为c1和c2的硬币同时超出限制的方案数+……
-……+面值为c1,c2,c3,c4的硬币同时超出限制的方案数
对于硬币ci，其超出限制的方案数为dp[x-c[i]*(d[i]+1)],然后容斥即可。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
LL dp[N],ans;
int T,x,d[5],c[5];
void dfs(int x,int k,int sum){
if(sum<0)return;
if(x==5){
if(k&1)ans-=dp[sum];
else ans+=dp[sum];
return;
}dfs(x+1,k+1,sum-(d[x]+1)*c[x]);
dfs(x+1,k,sum);
}
int main(){
for(int i=1;i<=4;i++)scanf("%d",&c[i]);
scanf("%d",&T);
dp[0]=1;
for(int i=1;i<=4;i++)for(int j=c[i];j<=100000;j++)dp[j]+=dp[j-c[i]];
while(T--){
for(int i=1;i<=4;i++)scanf("%d",&d[i]);
scanf("%d",&x); ans=0;
dfs(1,0,x);
printf("%lld
",ans);
}return 0;
}