[SHOI 2008] 循环的债务

题目大意

给定 AABBBBCCCCAA 的钱,以及每个人有的 1155101020205050100100 的钞票数量,求参与还清债务的最小钞票数,或输出 impossible 表示不能还清。

x1,  x2,  x31,000|x_1|,\;|x_2|,\;|x_3| \leqslant 1,000

总金额 1,000\leqslant 1,000

题目链接

【SHOI 2008】循环的债务 - Luogu 4026

题解

DP + 剪枝。

f(i,  a,  b)f(i, \; a, \; b) 表示正在考虑第 ii 种面值的钞票(从小到大)、AAaa 元、BBbb 元(由于金额不变,所以 CC 的钱数可以计算出来)时的答案。

枚举 ii ,枚举有意义的 aLastaLastbLastbLast ,我们要从 f(i1,  aLast,bLast)f(i - 1, \; aLast, bLast) 更新一些 f(i,xxx,xxx)f(i, xxx, xxx) 的答案。

只有六种转移:AB,CA \rightarrow B,CBC,AB \rightarrow C, ACA,BC \rightarrow A, BA,BCA, B \rightarrow CB,CAB, C \rightarrow AC,ABC, A \rightarrow B ,枚举给出去的钞票数并更新。

考虑剪枝,如果用剩下未考虑的钞票无论怎么凑都无法凑出当前金额,则直接跳过,判断是看金额是否是 d=gdc(100,  50)d = gdc(100, \; 50 \dots 当前面额) 的倍数,枚举金额时也每次增加 dd

代码

这题让我突然觉得两格缩进挺好的。。。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <climits>
#include <algorithm>
const int MAXS = 1005;
const int COIN = 6;
const int money[6] = {1, 5, 10, 20, 50, 100};
const int gcd[6] = {1, 5, 10, 10, 50, 100};
int f[2][MAXS][MAXS];
int coin[3][COIN], sm[3], tm[3], sum;
int dp() {
int curr = 0, last = curr ^ 1;
for (int i = 0; i < MAXS; i++) for (int j = 0; j < MAXS; j++) f[curr][i][j] = INT_MAX;
f[curr][sm[0]][sm[1]] = 0;
for (int i = 0; i < COIN; i++) {
curr ^= 1, last ^= 1;
for (int j = 0; j < MAXS; j++) for (int k = 0; k < MAXS; k++)
f[curr][j][k] = f[last][j][k];
int d = gcd[i], ca, cb;
for (ca = 0; (tm[0] - ca) % d; ca++);
for (cb = 0; (tm[1] - cb) % d; cb++);
if ((tm[2] - (sum - ca - cb)) % d) continue;
for (int aLast = ca; aLast < MAXS && sum - aLast - cb >= 0; aLast += d) {
for (int bLast = cb; bLast < MAXS && sum - aLast - bLast >= 0; bLast += d) {
int cLast = sum - aLast - bLast;
if (f[last][aLast][bLast] == INT_MAX) continue;
for (int a = 0; a <= coin[0][i] && a * money[i] <= aLast; a++) {
for (int b = 0; b <= a && bLast + b * money[i] < MAXS; b++) {
if (cLast + (a - b) * money[i] < MAXS)
f[curr][aLast - a * money[i]][bLast + b * money[i]]
= std::min(f[curr][aLast - a * money[i]][bLast + b * money[i]], f[last][aLast][bLast] + a);
}
}
for (int b = 0; b <= coin[1][i] && b * money[i] <= bLast; b++) {
for (int c = 0; c <= b && cLast + c * money[i] < MAXS; c++) {
if (aLast + (b - c) * money[i] < MAXS)
f[curr][aLast + (b - c) * money[i]][bLast - b * money[i]]
= std::min(f[curr][aLast + (b - c) * money[i]][bLast - b * money[i]], f[last][aLast][bLast] + b);
}
}
for (int c = 0; c <= coin[2][i] && c * money[i] <= cLast; c++) {
for (int a = 0; a <= c && aLast + a * money[i] < MAXS; a++) {
if (bLast + (c - a) * money[i] < MAXS)
f[curr][aLast + a * money[i]][bLast + (c - a) * money[i]]
= std::min(f[curr][aLast + a * money[i]][bLast + (c - a) * money[i]], f[last][aLast][bLast] + c);
}
}
for (int a = 0; a <= coin[0][i] && a * money[i] <= aLast; a++) {
for (int b = 0; b <= coin[1][i] && b * money[i] <= bLast; b++) {
if (cLast + (a + b) * money[i] < MAXS)
f[curr][aLast - a * money[i]][bLast - b * money[i]]
= std::min(f[curr][aLast - a * money[i]][bLast - b * money[i]], f[last][aLast][bLast] + a + b);
}
}
for (int b = 0; b <= coin[1][i] && b * money[i] <= bLast; b++) {
for (int c = 0; c <= coin[2][i] && c * money[i] <= cLast; c++) {
if (aLast + (b + c) * money[i] < MAXS)
f[curr][aLast + (b + c) * money[i]][bLast - b * money[i]]
= std::min(f[curr][aLast + (b + c) * money[i]][bLast - b * money[i]], f[last][aLast][bLast] + b + c);
}
}
for (int c = 0; c <= coin[2][i] && c * money[i] <= cLast; c++) {
for (int a = 0; a <= coin[0][i] && a * money[i] <= aLast; a++) {
if (bLast + (c + a) * money[i] < MAXS)
f[curr][aLast - a * money[i]][bLast + (c + a) * money[i]]
= std::min(f[curr][aLast - a * money[i]][bLast + (c + a) * money[i]], f[last][aLast][bLast] + c + a);
}
}
}
}
}
return f[curr][tm[0]][tm[1]];
}
int main() {
int owe[3];
for (int i = 0; i < 3; i++) scanf("%d", &owe[i]);
for (int i = 0; i < 3; i++) for (int j = COIN - 1; ~j; j--)
scanf("%d", &coin[i][j]), sm[i] += coin[i][j] * money[j];
sum = sm[0] + sm[1] + sm[2];
tm[0] = sm[0] - owe[0] + owe[2];
tm[1] = sm[1] - owe[1] + owe[0];
tm[2] = sm[2] - owe[2] + owe[1];
if (tm[0] < 0 || tm[1] < 0 || tm[2] < 0) return puts("impossible"), 0;
int ans = dp();
if (ans == INT_MAX) puts("impossible");
else printf("%d\n", ans);
return 0;
}