原题呈现

P1450 硬币购物#

题目描述#

共有 $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$ ．

输出格式#

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

输入输出样例 #1#

输入 #1#

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

输出 #1#

说明/提示#

数据规模与约定#

对于 $100\%$ 的数据，保证 $1 \leq c_i, d_i, s \leq 10^5$ ， $1 \leq n \leq 1000$ ．

我们发现这道题是一个物品数很少的多重背包问题，但显然，使用多重背包会超时．

因此，我们尝试将其转化为完全背包．

观察到完全背包和多重背包的区别只在于限制，我们先无视限制，跑一次完全背包．

1
dp[0] = 1;
2
for (int i = 1; i <= 4; i++) {
3
  for (int j = c[i]; j <= N; j++) {
4
    dp[j] += dp[j - c[i]];
5
  }
6
}

显然，这样的方案数比目标方案数大，多出了：

至少有 1 种数值的硬币超出限制

这样的方案．

为了计算出多出的方案数，我们可以使用容斥．定义 $f(s)$ 表示第 $i$ 种硬币（ $s$ 是一个集合且满足 $i \in s$ ）必须超出限制，其余不管．

则至少有 1 种数值的硬币超出限制的答案 $ans$ ：

\begin{align*} ans &= f(\{1\}) + f(\{2\}) + f(\{3\}) + f(\{4\})\\ &-(f(\{1,2\}) + f(\{1,3\}) + f(\{1,4\}) + f(\{2,3\}) + f(\{2,4\}) + f(\{3,4\}))\\ &+f(\{1,2,3\})+f(\{1,2,4\})+f(\{1,3,4\})+f(\{2,3,4\})\\ &-f(\{1,2,3,4\}) \end{align*}

最终答案为： $dp[s] - ans$ ．

问题是，如何求 $f(s)$ ？

以 $f(\{2,4\})$ 为例，需要统计第 2 种和第 4 种硬币超出限制的方案数，那么，只需要固定第 2 种有 $d[2]+1$ 个，用掉 $(d[2] + 1) \times c[2]$ 元，第 4 种有 $c[4]$ 个，用掉 $(d[4] + 1) \times c[4]$ 元，将这些当成已知，剩余的需要分配的元数为 $s' = s - (d[2] + 1) \times c[2] - (d[4] + 1) \times c[4]$ ， $f(\{2,4\})$ 就等于 $s'$ ．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 1e5 + 100;
5
int c1, c2, c3, c4, d1, d2, d3, d4, d5, s;
6
int dp[N], c[5], d[5];
7
// dp[i][j] 考虑到前i种硬币，总价值为j的方案数
8
// 不存在硬币超出 = 无限制 - (必须1种超出) + (必须2种超出) - (必须3种超出) +
9
// (必须4种超出)
10
signed main() {
11
    cin >> c[1] >> c[2] >> c[3] >> c[4];
12
    int T;
13
    cin >> T;
14
    dp[0] = 1;
15
    for (int i = 1; i <= 4; i++) {
16
        for (int j = c[i]; j <= N; j++) {
17
            dp[j] += dp[j - c[i]];
18
        }
19
    }
20
    while (T--) {
21
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
22
        int ans = 0;
23
        // 子集枚举
24
        for (int st = 0; st < (1 << 4); st++) {
25
            int cur = s, vaild = 0;
26
            for (int i = 0; i < 4; i++) {
27
                if (st & (1 << i)) {
28
                    vaild++;
29
                    cur -= (d[i + 1] + 1) * c[i + 1];
30
                }
31
            }
32
            if (cur >= 0)
33
                ans += (vaild % 2 ? -1 : 1) * dp[cur];
34
        }
35
        cout << ans << endl;
36
    }
37
}

正难则反，正着思考问题没有结果不妨反过来思考．

音乐

音乐

P1450 硬币购物#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

数据规模与约定#

文章分享

音乐

安吉D4-A

P1450 硬币购物#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

数据规模与约定#

文章分享