BZOJ 1042: [HAOI2008]硬币购物 (详解)（背包&容斥原理）

时间：2021-09-21 17:31:54

　　题面：https://www.cnblogs.com/fu3638/p/6759919.html

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西，

　　请问每次有多少种付款方法。其中di,s<=100000,tot<=1000。

　　题解：
　　　　首先考虑一个简单的问题，如果去掉题目中对于个数的限制，即给你四种面值的的硬币，问你有多少种方案能凑成
　　si的价值。欸我们瞬间发现这是个完全背包的裸题，那果断乱搞。
　　　　首先我们做一遍完全背包，定义f[i]为凑成i价值的方案数。
　　　　接下来回到原题，我们发现题目加了一个di的限制，那怎么办呢（摸摸脑袋）。
　　　　经过冷静的分析（查题解），发现这题可以用容斥原理乱搞。
　　　　通过容斥原理，我们得出ans=全部方案（不考虑限制（即f[ans]））-Σ一种面值超过限制的方案数+Σ两种超限-Σ三种超限+Σ四种超限。
　　　　那么如何求有几种超过限制的方案数呢
　　　　以一种面值超过限制的方案数为例，那么这一种（不妨设为第i种）至少用d[i]+1个，即产生c[i]*(d[i]+1)的价值。那么剩下的s-c[i]*(d[i]+1)（记为rest）
　　就可以随意取值，即为f[rest]种。
　　　　那么两种三种的就是f[rest](rest=s-Σc[i]*(d[i]+1))。
　　　　tip:枚举方案可以用位运算。
　　代码： 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxs=;

ll ans,f[maxs+];

int c[],d[],tot,s;

int main(){

    scanf("%d%d%d%d%d",&c[],&c[],&c[],&c[],&tot);

    //完全背包预处理

    f[]=;

    for(int i=;i<=;i++)

        for(int j=c[i];j<=maxs;j++)

            f[j]+=f[j-c[i]]; 

    for(int k=;k<=tot;k++){

        scanf("%d%d%d%d%d",&d[],&d[],&d[],&d[],&s);

        ans=;

        for(int i=;i<(<<);i++){

            int rest=s,tt=i,num=,pos=;

            while(tt){

                pos++;//第几枚硬币

                if(tt&) rest-=c[pos]*(d[pos]+),num++;//num->几枚有限制

                tt>>=;

            }

            if(rest<) continue;

            if(num&) ans-=f[rest];

            else ans+=f[rest];

        }

        printf("%lld\n",ans);

    }

    return ;

}

　　参考：

　　　　https://blog.csdn.net/aarongzk/article/details/51511564

　　　　　https://blog.csdn.net/doctor_godder/article/details/50071749


相关文章