[SHOI2008] 循环的债务

GitHub 跳转原题关系图返回列表

把每张钞票看成独立物品，做 2 维 DP：dp[a][b] 表示最终分给 Alice 金额为 a、Bob 金额为 b 时最多能保留多少张原主人不变的钞票，答案是总张数减去最多保留张数。

OJ: luogu

题目 ID: P4026

难度:提高+/省选-

标签:动态规划背包状态设计分类讨论

日期: 2026-06-21 10:28

题意

三个人互相之间有循环债务，同时每个人手里有一些不同面额的钞票。

现在要通过重新分配这些钞票来清偿债务，要求每个人最终持有的钱数恰好等于清债后的目标金额。

代价是“发生交换的钞票张数”。
求最少需要交换多少张钞票；如果无解，输出 impossible。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int INF_NEG = -1000000000;

struct Bill {
    int value;
    int owner;
};

int x1, x2, x3;
int cnt[3][6];
int deno[6] = {100, 50, 20, 10, 5, 1};
vector<Bill> bills;
int target_a, target_b, target_c;
int total_bills;
int answer_stay;

void dfs(int idx, int a, int b, int c, int stay) {
    if (idx == (int) bills.size()) {
        if (a == target_a && b == target_b && c == target_c) {
            answer_stay = max(answer_stay, stay);
        }
        return;
    }

    int v = bills[idx].value;
    int owner = bills[idx].owner;

    if (a + v <= target_a) {
        dfs(idx + 1, a + v, b, c, stay + (owner == 0));
    }
    if (b + v <= target_b) {
        dfs(idx + 1, a, b + v, c, stay + (owner == 1));
    }
    if (c + v <= target_c) {
        dfs(idx + 1, a, b, c + v, stay + (owner == 2));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 把每张钞票看成独立物品，枚举它最终留给 Alice / Bob / Cynthia 的哪一个人。
    cin >> x1 >> x2 >> x3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> cnt[i][j];
        }
    }

    int init_money[3] = {0, 0, 0};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 6; j++) {
            init_money[i] += cnt[i][j] * deno[j];
            total_bills += cnt[i][j];
            for (int t = 0; t < cnt[i][j]; t++) {
                bills.push_back({deno[j], i});
            }
        }
    }

    target_a = init_money[0] - x1 + x3;
    target_b = init_money[1] + x1 - x2;
    target_c = init_money[2] + x2 - x3;

    if (target_a < 0 || target_b < 0 || target_c < 0) {
        cout << "impossible\n";
        return 0;
    }

    answer_stay = INF_NEG;
    dfs(0, 0, 0, 0, 0);

    if (answer_stay == INF_NEG) {
        cout << "impossible\n";
    } else {
        cout << total_bills - answer_stay << '\n';
    }

    return 0;
}

这题最适合的视角不是“钱怎么传”，而是：

每张钞票最后归谁？

如果一张钞票最后还留在原主人手里，那么它就没有被交换。
所以目标就变成：

在满足三个人最终金额要求的前提下，尽量让更多钞票留在原主人手里。

设三个人最终应该持有的钱分别是：

target_a
target_b
target_c

这三个值可以从输入债务直接算出来。

接着把每张钞票看成一个独立物品。
做一个二维 DP：

dp[a][b] = 当前已经处理完若干张钞票，最终分给 Alice 金额为 a、分给 Bob 金额为 b 时，最多有多少张钞票没换主人

那么分给 Cynthia 的金额就由“已处理总金额 - a - b”唯一确定。

处理一张钞票时有三种选择：最终给 Alice、Bob 或 Cynthia。
如果给的人正好是原主人，那么“保留原主人不变的张数”就加一。

最终如果 dp[target_a][target_b] 可达，那么：

最少交换张数 = 总张数 - 最多保留张数

DP 转移方程

核心状态：

dp[a][b] 为 Alice 金额 a、Bob 金额 b 时最多保留数

核心转移：

每张钞票分别尝试给 A/B/C，给原主人则 +1

答案收束：

总张数-dp[target_a][target_b]

代码

cpp

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114#include <bits/stdc++.h>
using namespace std;

const int INF_NEG = -1000000000;

struct Bill {
    int value;
    int owner;
};

int x1, x2, x3;
int cnt[3][6];
int deno[6] = {100, 50, 20, 10, 5, 1};
vector<Bill> bills;
vector<int> dp, ndp;

int id(int a, int b, int lim_b) {
    return a * (lim_b + 1) + b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> x1 >> x2 >> x3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> cnt[i][j];
        }
    }

    int init_money[3] = {0, 0, 0};
    int total_value = 0;
    int total_bills = 0;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 6; j++) {
            init_money[i] += cnt[i][j] * deno[j];
            total_value += cnt[i][j] * deno[j];
            total_bills += cnt[i][j];
            for (int t = 0; t < cnt[i][j]; t++) {
                bills.push_back({deno[j], i});
            }
        }
    }

    int target_a = init_money[0] - x1 + x3;
    int target_b = init_money[1] + x1 - x2;
    int target_c = init_money[2] + x2 - x3;

    if (target_a < 0 || target_b < 0 || target_c < 0 ||
        target_a + target_b + target_c != total_value) {
        cout << "impossible\n";
        return 0;
    }

    dp.assign((target_a + 1) * (target_b + 1), INF_NEG);
    ndp.assign((target_a + 1) * (target_b + 1), INF_NEG);
    dp[id(0, 0, target_b)] = 0;

    int processed_value = 0;

    for (size_t idx = 0; idx < bills.size(); idx++) {
        fill(ndp.begin(), ndp.end(), INF_NEG);
        int v = bills[idx].value;
        int owner = bills[idx].owner;

        int max_a = min(target_a, processed_value);
        for (int a = 0; a <= max_a; a++) {
            int low_b = processed_value - a - target_c;
            if (low_b < 0) {
                low_b = 0;
            }
            int high_b = processed_value - a;
            if (high_b > target_b) {
                high_b = target_b;
            }
            for (int b = low_b; b <= high_b; b++) {
                int cur = dp[id(a, b, target_b)];
                if (cur == INF_NEG) {
                    continue;
                }

                if (a + v <= target_a) {
                    int &ref = ndp[id(a + v, b, target_b)];
                    ref = max(ref, cur + (owner == 0));
                }

                if (b + v <= target_b) {
                    int &ref = ndp[id(a, b + v, target_b)];
                    ref = max(ref, cur + (owner == 1));
                }

                int next_c = processed_value + v - a - b;
                if (next_c <= target_c) {
                    int &ref = ndp[id(a, b, target_b)];
                    ref = max(ref, cur + (owner == 2));
                }
            }
        }

        processed_value += v;
        dp.swap(ndp);
    }

    int stay_best = dp[id(target_a, target_b, target_b)];
    if (stay_best == INF_NEG) {
        cout << "impossible\n";
    } else {
        cout << total_bills - stay_best << '\n';
    }

    return 0;
}

复杂度

设总金额不超过 S，这里 S <= 1000。

DP 状态数是 $O(target_a * target_b)$ ，总复杂度约为：

$O(总钞票数 * target_a * target_b)$

在本题数据范围内可以通过。

总结

这题的关键是把“最少交换张数”转成“最多保留多少张原主人不变的钞票”。

一旦换这个角度，题目就变成非常标准的逐张物品分配 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P4026 [SHOI2008] 循环的债务

题目描述

Alice、Bob 和 Cynthia 总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过，鉴别钞票的真伪是一件很麻烦的事情，于是他们决定要在清还债务的时候尽可能少的交换现金。

比如说，Alice 欠 Bob $10$ 元，而 Cynthia 和他俩互不相欠。现在假设 Alice 只有一张 $50$ 元，Bob 有 $3$ 张 $10$ 元和 $10$ 张 $1$ 元，Cynthia有 $3$ 张 $20$ 元。一种比较直接的做法是：Alice 将 $50$ 元交给 Bob，而 Bob 将他身上的钱找给 Alice，这样一共就会有 $14$ 张钞票被交换。但这不是最好的做法，最好的做法是：Alice 把 $50$ 块给 Cynthia，Cynthia 再把两张 $20$ 给 Alice，另一张 $20$ 给 Bob，而 Bob 把一张 $10$ 块给 Cynthia，此时只有 $5$ 张钞票被交换过。

没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。

输入格式

输入的第一行包括三个整数： $x_1$ 、 $x_2$ 、 $x_3$ （ $-1,000 \le x_1, x_2, x_3 \le 1,000$ ），其中

$x_1$ 代表 Alice 欠 Bob 的钱（如果 $x_1$ 是负数，说明 Bob 欠了 Alice 的钱）

$x_2$ 代表 Bob 欠 Cynthia 的钱（如果 $x_2$ 是负数，说明 Cynthia 欠了 Bob 的钱）

$x_3$ 代表 Cynthia 欠 Alice 的钱（如果 $x_3$ 是负数，说明 Alice 欠了 Cynthia 的钱）

接下来有三行，每行包括 6 个自然数：

$ a_{100}, a_{50}, a_{20}, a_{10}, a_5, a_1 $

$ b_{100}, b_{50}, b_{20}, b_{10}, b_5, b_1 $

$ c_{100}, c_{50}, c_{20}, c_{10}, c_5, c_1 $

$a_{100}$ 表示 Alice 拥有的 $100$ 元钞票张数， $b_{50}$ 表示 Bob 拥有的 $50$ 元钞票张数，以此类推。另外，我们保证有 $a_{10} + a_5 + a_1 \le 30$ ， $b_{10} + b_5 + b_1 \le 30$ ， $c_{10} + c_5 + c_1 \le 30$ ，而且三人总共拥有的钞票面值总额不会超过 $1,000$ 。

输出格式

如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。

输入输出样例 #1

输入 #1

text

1
2
3
410 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

输出 #2

text

说明/提示

对于 $30\%$ 的数据， $x_1, x_2, x_3 \le 50$ 。

对于 $100\%$ 的数据， $x_1, x_2, x_3 \le 1,000$ 。

[SHOI2008] 循环的债务

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析