题目链接：bzoj1042 题目大意： 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
题解：dp预处理+容斥原理 首先假设它没有个数的限制，预处理出f[i]表示得到i价值的东西有多少种方案。 有了限制的话，就可以用容斥解决。 ans=f[s]-Σf[d[i]超过限制的]+Σf[d[i],d[j]都超过限制的]-Σf(三个都超过限制的)+Σf(四个都超过限制的) 怎么算Σf[d[i]超过限制的]呢？ 比如要让1超过限制的话，只要令1的个数一定超过d[1]，那么剩下的就可以随便了。于是f[d[1]超过限制的]=fs-(d[1]+1)*c[1]。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; #define maxn 100100 LL c[5],d[5],f[maxn],ans; void dfs(int x,int t,int sum) { if (x>4) { if (t&1) ans-=f[sum]; else ans+=f[sum]; return; } dfs(x+1,t,sum); if (sum>=(d[x]+1)*c[x]) dfs(x+1,t+1,sum-(d[x]+1)*c[x]); } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int i,j,tot,n=4;LL s; memset(f,0,sizeof(f));f[0]=1; for (i=1;i<=n;i++) { scanf("%lld",&c[i]); for (j=c[i];j<=100000;j++) f[j]+=f[j-c[i]]; } scanf("%d",&tot); while (tot--) { for (i=1;i<=4;i++) scanf("%lld",&d[i]); scanf("%lld",&s); ans=0;dfs(1,0,s); printf("%lld\n",ans); } return 0; }