BZOJ 1042 [HAOI2008] 硬币购物

Description

　　硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s i的价值的东西。请问每次有多少种付款方法。

Input

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

　　每次的方法数

Sample Input

1 2 5 10 2 3 2 3 1 10 1000 2 2 2 900

Sample Output

4 27

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP+容斥原理+思路~

先DP预处理出不限制使用次数的情况数，用f[i]表示i元的情况数，那么f[i]=sum{f[i-c[j]]}，其中i>=c[j]，f[0]=1。

f数组的更新要按照基本法硬币的种类数，防止情况重复。

然后，对于每次花费，答案为没有超过的种类数-超过1种的种类数+超过2种的种类数-超过3种的种类数+超过4种的种类数（这里均为“至少”），dfs一下即可，要注意sum<0的情况。

f数组和ans都要开long long！

#include<cstdio> #include<iostream> using namespace std; #define ll long long int n,c[5],d[5],s; ll ans,f[100001]; 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<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void dfs(int u,int v,int sum) { if(sum<0) return; if(u==5) { ans+=(ll)((v&1) ? -f[sum]:f[sum]); return; } dfs(u+1,v^1,sum-c[u]*(d[u]+1));dfs(u+1,v,sum); } int main() { for(int i=1;i<=4;i++) c[i]=read();n=read();f[0]=1; for(int i=1;i<=4;i++) for(int j=1;j<=100000;j++) f[j]+=j>=c[i] ? f[j-c[i]]:0; while(n--) { for(int i=1;i<=4;i++) d[i]=read();s=read(); ans=0;dfs(1,0,s); printf("%lld\n",ans); } return 0; }