[HAOI 2008] 硬币购物

题目大意

硬币购物一共有 44 种硬币。面值分别为 c1c_1c2c_2c3c_3c4c_4。某人去商店买东西,去了 tottot 次。每次带 did_icic_i 硬币,买 sis_i 的价值的东西。请问每次有多少种付款方法。

1tot1,0001 \leqslant tot \leqslant 1,000

di,  s10,000d_i, \; s \leqslant 10,000

题目链接

【HAOI 2008】硬币购物 - Luogu 1450

题解

DP + 容斥原理。

f[i,  j]f[i, \; j] 为用前 ii 种硬币凑出价值 jj 的方案数(不考虑硬币数量限制),则转移为:

f[i, \; j] = \begin{cases} \begin{align} f[i - 1, \; j] \quad &j < c_i \\ f[i - 1, \; j] + f[i - 1, \; j - c_i] \quad &j \geqslant c_i \end{align} \end{cases}

现考虑数量限制,用容斥原理:不考虑限制的方案数 - 考虑有一种硬币超过限制的方案数 + 考虑有两种硬币超过限制的方案数 - 考虑有三种硬币超过限制的方案数 + 考虑有四种硬币超过限制的方案数。

对于考虑有一种硬币超过限制的方案数,我们让一种硬币先用 di+1d_i + 1 次,剩下的随意,那方案数就是:

f[4,  s(di+1)×ci]f[4, \; s - (d_i + 1) \times c_i]

代码

答案会超int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
const int MAXS = 100005;
int main() {
int c[5], tot;
scanf("%d %d %d %d %d", &c[1], &c[2], &c[3], &c[4], &tot);
static long long f[5][MAXS];
f[0][0] = 1;
for (int i = 1; i <= 4; i++) for (int j = 0; j < MAXS; j++) {
if (j < c[i]) f[i][j] = f[i - 1][j];
else f[i][j] = f[i - 1][j] + f[i][j - c[i]];
}
while (tot--) {
int d[5], s;
scanf("%d %d %d %d %d", &d[1], &d[2], &d[3], &d[4], &s);
long long ans = f[4][s];
for (int i = 1; i <= 4; i++) d[i]++;
for (int i = 1; i <= 4; i++) {
if (s - d[i] * c[i] >= 0) ans -= f[4][s - d[i] * c[i]];
}
for (int i = 1; i <= 4; i++) for (int j = i + 1; j <= 4; j++) {
if (s - d[i] * c[i] - d[j] * c[j] >= 0)
ans += f[4][s - d[i] * c[i] - d[j] * c[j]];
}
int temp = 0;
for (int i = 1; i <= 4; i++) temp += d[i] * c[i];
for (int i = 1; i <= 4; i++) {
if (s - temp + d[i] * c[i] >= 0)
ans -= f[4][s - temp + d[i] * c[i]];
}
if (s - temp >= 0) ans += f[4][s - temp];
printf("%lld\n", ans);
}
return 0;
}