[SHOI 2008] 循环的债务

发表于2017-05-08更新于2020-08-06

题目大意

给定 AA 欠 BB 、BB 欠 CC 、CC 欠 AA 的钱，以及每个人有的 11 、55 、1010 、2020 、5050 、100100 的钞票数量，求参与还清债务的最小钞票数，或输出 impossible 表示不能还清。

∣x1∣,  ∣x2∣,  ∣x3∣⩽1,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 种面值的钞票（从小到大）、AA 有 aa 元、BB 有 bb 元（由于金额不变，所以 CC 的钱数可以计算出来）时的答案。

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

只有六种转移：A→B,CA \rightarrow B,C、B→C,AB \rightarrow C, A、C→A,BC \rightarrow A, B、A,B→CA, B \rightarrow C、B,C→AB, C \rightarrow A、C,A→BC, 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;
}