Luogu-P1450-硬币购物

题目 P1450 [HAOI2008] 硬币购物

题目描述

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西，去了 $n$ 次，对于每次购买，他带了 $d_i$ 枚 $i$ 种硬币，想购买 $s$ 的价值的东西。请问每次有多少种付款方法。

输入格式

输入的第一行是五个整数，分别代表 $c_1,c_2,c_3,c_4, n$。

接下来 $n$ 行，每行有五个整数，描述一次购买，分别代表 $d_1, d_2, d_3, d_4,s$。

输出格式

对于每次购买，输出一行一个整数代表答案。

思路：背包dp

使用完全背包

第一眼看像是多重背包，但是又不太对。

多重背包的本质是0/1背包，但是0/1背包会导致重复计数。

例如，如果有两个价值为 $1$ 的硬币，那么这两枚硬币就会全部计算一次，而根据题意，这种情况只能算一次。

所以，本题应用完全背包，之后再减掉不合理的方案数才是最优解。

不合理的方案

根据题意，当使用第 $j$ 枚硬币的数量超过了 $d[j]$ 时，方案不合理。

所以，从数量在 $d[j] + 1$ 以上的时候，应该减去这部分的方案数。

简化

如果限制只有一种硬币，使用 $dp[x]$ 表示钱数为 $x$ 时的方案数，不难发现，转移方案数的时候，需要一个钱数加上硬币的价值。

因此，需要减掉的部分为 $dp[x - c[i] \cdot (d[i] + 1)]$。

因为数量更多的情况已经可以转移到 $dp[x - c[i] \cdot (d[i] + 1)]$ 了，所以不应该额外减掉剩下的。

• 数量更多，也就意味着需要减的更多，所以下标更小，可以转移到下标更大的上。

另外，需要注意的是，存在 $c[i] \cdot (d[i] + 1) > x$ 的情况，即硬币还没用完就超过了 $x$。这种情况需要特殊判断。

复原

回到原题，如果有四种硬币呢？

如果每种硬币都减的话，会多减交叉部分。如果硬币 $1$ 和硬币 $2$ 都限制了数量，它们的交叉部分重复减了两次。

也就是说，还要额外加上它们的交叉部分$dp[x-c[1] \cdot (d[1]+1)-c[2] \cdot (d[2]+1)]$。

同理，其它硬币的交叉部分也要加上。

此时又引发了一个问题，$1,2$、$1,3$、$2,3$ 的交叉部分 $1,2,3$ 加回去两次，也要减掉才行，其余情况及子情况同理。

仔细思考一下，这就是容斥原理啊！

对于不同硬币的处理

由于只存在四种硬币，我们可以考虑使用状态压缩（怎么又是你）。

ll ans = 0;
for(int i = 0; i < (1 << 4); i++) {
    int offset = 0;
    int t = 1;
    for(int j = 0; j < 4; j++) {
        if(i & (1 << j)) offset += c[j] * (d[j] + 1), t *= -1;
    }
    if(offset > s) continue;
    ans += dp[s - offset] * t;
}
cout << ans << endl;

这里的 $t$ 就是判断当前是需要加上还是减去的。

不难发现，奇数种硬币要减去，偶数种硬币要加上。

AC Code

// template v9
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 4;
const int M = 1e5 + 10;

int c[N];
int d[N];
ll dp[M];

int main() {

#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    dp[0] = 1;
    for(int i = 0; i < 4; i++) {
        cin >> c[i];
        for(int j = c[i]; j < M; j++) {
            dp[j] += dp[j - c[i]];
        }
    }
    int n, s;
    cin >> n;
    while(n-- > 0) {
        for(int i = 0; i < 4; i++) {
            cin >> d[i];
        }
        cin >> s;
        ll ans = 0;

        for(int i = 0; i < (1 << 4); i++) {
            int offset = 0;
            int t = 1;
            for(int j = 0; j < 4; j++) {
                if(i & (1 << j)) offset += c[j] * (d[j] + 1), t *= -1;
            }
            if(offset > s) continue;
            ans += dp[s - offset] * t;
        }
        cout << ans << endl;
    }
    return 0;
}