首页 > 代码库 > [bzoj1042][HAOI2008][硬币购物] (容斥原理+递推)
[bzoj1042][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 23 2 3 1 101000 2 2 2 900
Sample Output
427
Solution
先递推一下哈
用递推式f[s]+=f[s-c[i]]，求出没有个数限制情况下达到价值s的方案数
那么，有限制的方案数=f[s]-超过硬币1限制的方案数-超过硬币2限制的方案数-超过硬币3限制的方案数-超过硬币4限制的方案数+超过硬币1、2限制的方案数+超过硬币1、3限制的方案数+超过硬币1、4限制的方案数+。。。+超过硬币1、2、3、4限制的方案数
那么，对于超过情况
设s[i]代表第i种硬币的限制个数，c[i]代表第i种硬币的价值
我们只考虑超过s[i]+1的情况，剩下tot-c[i]*(s[i]+1)的话就自由分配
很科学吧
#include <stdio.h>#define MaxN 100010#define MaxBuf 1<<22#define L long long#define Blue() ((S==T&&(T=(S=B)+fread(B,1,MaxBuf,stdin),S==T))?0:*S++)char B[MaxBuf],*S=B,*T=B;template<class Type>inline void Rin(Type &x){ x=0;int c=Blue();bool b=0; for(;c<48||c>57;c=Blue()) if(c==45)b=1; for(;c>47&&c<58;c=Blue()) x=(x<<1)+(x<<3)+c-48; x=b?-x:x;}int c[4],s[4],tar,kase;L f[MaxN],ans;void dfs(int x,int y,int sum){ if(sum<0) return; if(x==4){ ans+=y&1?-f[sum]:f[sum]; return; } dfs(x+1,y,sum); dfs(x+1,y+1,sum-c[x]*(s[x]+1));}#define FO(x) {freopen(#x".in","r",stdin);}int main(){ FO(bzoj1042); for(int i=0;i<4;i++) Rin(c[i]); f[0]=1; for(int i=0;i<4;i++) for(int j=c[i];j<=100000;j++) f[j]+=f[j-c[i]]; Rin(kase); while(kase--){ for(int i=0;i<4;i++) Rin(s[i]); Rin(tar); ans=0; dfs(0,0,tar); printf("%lld\n",ans); } return 0;}
[bzoj1042][HAOI2008][硬币购物] (容斥原理+递推)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。