硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买s i的价值的东西。请问每次有多少种付款方法。
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000
每次的方法数
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; }