BZOJ1042 [HAOI2008]硬币购物 完全背包 容斥原理

时间：2021-04-09 22:17:13

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1042

题目概括

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

题解

　　一开始没看数据范围，觉得是类似状压的dp。

　　然后看了看数据范围，懵逼了。

　　然后发现可以写容斥！

　　我们先当作完全背包，不考虑限制，把花费每种价格的方案数弄出来。

　　然后容斥一下就可以了。

　　具体容斥：所有情况 - 第一种货币超限的 - 第二种货币超限的…… + 第1、2种货币都超限的………………

代码

连续5次1A了，庆祝一下。

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

typedef long long LL;

const int N=,N_size=N+;

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

LL dp[N_size];

int main(){

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

    memset(dp,,sizeof dp);

    dp[]=;

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

        for (int j=;j<=N;j++)

            if (j+c[i]<=N)

                dp[j+c[i]]+=dp[j];

    while (tot--){

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

        LL ans=;

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

            int v=s,cnt=;

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

                if ((i>>j)&)

                    cnt++,v-=(d[j]+)*c[j];

            if (v<)

                continue;

            if (cnt&)

                ans-=dp[v];

            else

                ans+=dp[v];

        }

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

    }

    return ;

}

相关文章