首页 > 代码库 > BZOJ 1042 硬币购物(完全背包+DP)

BZOJ 1042 硬币购物(完全背包+DP)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1042

题意:给出四种面值的硬币c1,c2,c3,c4。n个询问。每次询问用d1、d2、d3、d4个相应的硬币能够拼出多少种总和为s?

思路:(1)首先,用完全背包求出f[i]表示四种硬币的数量无限制拼出i的方案数。

(2)接着我们来理解 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得到的。

(3)现在根据我们使用完全背包求出的f 值,是没有考虑每种使用的数量,但是现在有了di的限制,我们就要减去那些不满足限制的。我们用一个4位的二进制表示状态的话,每位上为1表示第i种硬币 的数量满足不超过di的限制,那么我们就是要得到1111,而我们求出的f[s]其实是0000,那么我们怎么由0000得到1111呢?容斥原 理:1111=0000-(1000+0100+0010+0001)+ (1100+1010+1001+0110+0101+0011)-(1110+1101+1011+0111)+(1111)。

 

int n,c[5],d[5],s;i64 f[N],ans;void DP(){    f[0]=1;    int i,j;    FOR1(i,4) for(j=c[i];j<N;j++)    {        f[j]+=f[j-c[i]];    }}i64 F(int x){    if(x>=0) return f[x];    return 0;}int main(){    int i,j,k;    FOR1(i,4) RD(c[i]); DP();    RD(n);    while(n--)    {        FOR1(i,4) RD(d[i]),d[i]=(d[i]+1)*c[i];        RD(s);        ans=F(s);        FOR1(i,4) ans-=F(s-d[i]);        FOR1(i,4) FOR(j,i+1,4) ans+=F(s-d[i]-d[j]);        FOR1(i,4) FOR(j,i+1,4) FOR(k,j+1,4) ans-=F(s-d[i]-d[j]-d[k]);        ans+=F(s-d[1]-d[2]-d[3]-d[4]);        PR(ans);    }    return 0;}