BZOJ 1042: [HAOI2008]硬币购物 容斥+背包

时间：2021-03-02 22:13:44

1042: [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 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

HINT

 
题解：
　　首先不考虑取得硬币数量，背包求出f[s] 组成s元的方案数
　　然后考虑容斥：面值S的超过限制的方案数 – 第1种硬币超过限制的方案数 – 第2种硬币超过限制的方案数 – 第3种硬币超过限制的方案数 – 第4种硬币超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。
　　by HZWER 
#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

typedef unsigned long long ULL;

const long long INF = 1e18+1LL;

const double pi = acos(-1.0);

const int N = 2e5+, M = 1e3+,inf = 2e9;

LL f[N],ans;

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

void dfs(int i,int num,int sum) {

    if(sum < ) return ;

    if(i == ) {

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

        else ans += f[sum];

        return ;

    }

    dfs(i+,num+,sum - (d[i]+)*c[i]);

    dfs(i+,num,sum);

}

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 <= ; ++j) {

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

        }

    }

    while(tot--) {

        cin>>d[]>>d[]>>d[]>>d[]>>s;

        ans = ;

        dfs(,,s);

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

    }

    return ;

}
 

相关文章