bzoj 1042: [HAOI2008]硬币购物 dp+容斥原理

题目链接

1042: [HAOI2008]硬币购物

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1706 Solved: 985
[Submit][Status][Discuss]

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

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

和cf451E有点像。

先dp预处理出每种钱没有个数要求下的付款方法的个数。然后容斥，有某1种钱超过个数， 2种超过个数...4种超过个数的情况都算出来。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

int a[], b[], s;

ll dp[];

ll solve() {

    ll ret = ;

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

        int cnt = , sum = s;

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

            if((<<j)&i) {

                cnt++;

                sum -= a[j]*(b[j]+);

            }

        }

        if(sum<)

            continue;

        if(cnt&) {

            ret -= dp[sum];

        } else {

            ret += dp[sum];

        }

    }

    return ret;

}

int main()

{

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

        scanf("%d", &a[i]);

    }

    int n;

    cin>>n;

    dp[] = ;

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

        for(int j = a[i]; j<=; j++) {

            dp[j] += dp[j-a[i]];

        }

    }

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

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

            scanf("%d", &b[j]);

        }

        scanf("%d", &s);

        cout<<solve()<<endl;;

    }

    return ;

}

秒客网