【HAOI2008】硬币购物

妖狐艹你老母 2023-06-05 08:54 2阅读 0赞

# Description #

[【HAOI2008】硬币购物][HAOI2008]

给定4种硬币的价值。若干组询问，每次给出4种硬币的数量和要购买的花费，求恰好购买的方案数

# Solution #

背包dp计数+容斥

如果不考虑硬币数量的限制，那么这个问题就是完全背包方案数问题，一遍dp就可以解决

现在加上数量的限制，那么合法方案数就是总数-非法方案数

总数很简单，就是完全背包方案总数

考虑非法方案数，如果一个方案非法，肯定有一种或几种硬币超出限制，那么我们假定他们用了max+1

那么利用容斥原理，非法方案数=一种硬币超出-两种硬币超出+三种硬币超出……

时间复杂度$O(4maxS+tot\\times 4\\times 2^4)$

# Code #

#include <bits/stdc++.h>
    namespace shl {
        typedef long long ll;
        const int S = 1e5 + 10;
        int c[5], tot, d[5], s;
        ll f[S];
        inline int read() {
            int ret = 0, op = 1;
            char c = getchar();
            while (!isdigit(c)) {
                if (c == '-') op = -1; 
                c = getchar();
            }
            while (isdigit(c)) {
                ret = (ret << 3) + (ret << 1) + c - '0';
                c = getchar();
            }
            return ret * op;
        }
        int main() {
            for (register int i = 0; i < 4; ++i) c[i] = read();
            f[0] = 1ll;
            for (register int i = 0; i < 4; ++i)
                for (register int j = c[i]; j < S; ++j)
                    f[j] += f[j - c[i]];
            tot = read();
            while (tot--) {
                for (register int i = 0; i < 4; ++i) d[i] = read();
                s = read();
                ll ans = f[s];
                for (register int i = 1; i < 16; ++i) {
                    ll sum = s; 
                    int op = 0;
                    for (register int j = 0; j < 4; ++j)
                        if (i & (1 << j)) {
                            sum -= (d[j] + 1) * c[j];
                            op ^= 1;
                        }
                    if (sum < 0) continue ;
                    if (op) ans -= f[sum];
                    else ans += f[sum];
                } 
                printf("%lld\n", ans);
            }
            return 0;
        }
    };
    int main() {
        shl :: main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11383706.html

[HAOI2008]: https://www.luogu.org/problem/P1450