Description
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。
Input
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
Output
每次的方法数
Sample Input
3 2 3 1 10
1000 2 2 2 900
Sample Output
27
HINT
数据规模
di,s<=100000
tot<=1000
题解
感觉自己容斥原理根本不会……所以找道题做做。
正解完全背包+容斥。
首先完全背包可以让我们得到四种硬币数量不限时,组成s的方案。但我们要的是四种硬币均满足限制。
设某种或某几种硬币满足限制的方案数为集合Xi,则我们要求的为X1∩X2∩……∩Xn,我们已知总集合N满足| N |=f[m]。
以下摘自http://www.verydemo.com/demo_c92_i266806.html
接着我们来理解x=f[s]-f[s-(d1+1)*c1]的含义:x表示c1硬币的数量不超过d1个而其他三种硬币的数量不限制拼成s的方案数。我们举着例子来说明,假设现在有两种硬币,面值分别为1和2,那么我们求出f:f[0]=1,f[1]=1,f[2]=2,f[3]=2,f[4]=3,f[5]=3,f[6]=4。其中f[3]的两种分别为3=1+1+1=1+2,f[6]的四种为:6=1+1+1+1+1+1=1+1+1+1+2=1+1+2+2=2+2+2。加入我们现在求第一种硬币最多使用两个,第二种硬币无限制的方案数,按照我们说的x=f[6]-f[6--(2+1)*1]=f[6]-f[3]=2。也就是6=1+1+2+2=2+2+2两种。我们发现我们删除了1+1+1+1+1+1和1+1+1+1+2两种,为什么能够通过减去f[3]删掉这两种?我们来看f[3],3=1+1+1=1+2,我们发现6中被删掉的两种正是通过这个f[3]增加3个1得到的。
若我们用一个4位的二进制表示状态的话,每位上为1表示第i种硬币的数量满足不超过di的限制,0表示无限制,那么我们就是要得到1111,而我们求出的f[s]其实是0000,那么我们怎么由0000得到1111呢?容斥原理:1111=0000-(1000+0100+0010+0001)+(1100+1010+1001+0110+0101+0011)-(1110+1101+1011+0111)+(1111)。
PS:根据以下式子:
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define ll long long using namespace std; int c[4],n,s[4],m; ll f[100002],ans; void dp() { f[0]=1; int i,j; for(j=0;j<4;j++) for(i=c[j];i<=100000;i++) f[i]+=f[i-c[j]]; } void dfs(int w,int num,int k) { if(num<0) return; if(w==4) {if(k) ans-=f[num]; else ans+=f[num]; return ; } dfs(w+1,num,k); dfs(w+1,num-c[w]*(s[w]+1),k^1); } int main() { scanf("%d%d%d%d",&c[0],&c[1],&c[2],&c[3]); scanf("%d",&n); dp(); int i; for(i=1;i<=n;i++) {scanf("%d%d%d%d",&s[0],&s[1],&s[2],&s[3]); scanf("%d",&m); ans=0; dfs(0,m,0); printf("%lld\n",ans); } return 0; }