A，B，C 三个人之间互相有一些债务，每个人有面值为 $1, 5, 10, 20, 50, 100$ 的钞票若干，求出他们之间钞票交换次数最少的交换方式。

题解

最开始看到这道题的时候，我还以为这题是网络流。。现在看看我还是 too young..

好吧可以说团长的DP是真的好差。。

这道题的初始状态就像题目描述中说的那样，终止状态应该是 A，B，C 各自还清债务又收回欠款，由于欠款可以用一个 DAG 来描述（若成环则去掉环中权值最小的边），所以终止状态下 A，B，C 拥有的钱的数目是一定的，所以尝试使用钱数作为状态。

设 $f(i, a, b)$ 为使用前 $i$ 种面值的钞票，使得 $A$ 有 $a$ 元， $B$ 有 $b$ 元的最小交换次数。

枚举交换方式，有如下几种交换：

其中 $a \rightarrow b$ 意为 $a$ 把钱给 $b$ 。

代码

#include <cstdio>
#include <climits>
#include <algorithm>
const int MAX_M = 1000;
const int VAL[] = { -1, 1, 5, 10, 20, 50, 100 };
int sum[3], own[3][6 + 1];
int tot;
int f[6 + 1][MAX_M + 1][MAX_M + 1];
int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if (a > 0 && b > 0 && c > 0) {
        int min = std::min(std::min(a, b), c);
        a -= min, b -= min, c -= min;
    } else if (a < 0 && b < 0 && c > 0) {
        int max = std::max(std::max(a, b), c);
        a -= max, b -= max, c -= max;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 6; j++) {
            scanf("%d", &own[i][6 - j]);
            sum[i] += own[i][6 - j] * VAL[6 - j];
        }
        tot += sum[i];
    }
    for (int i = 0; i <= 6; i++)
        for (int j = 0; j <= MAX_M; j++)
            for (int k = 0; k <= MAX_M; k++)
                f[i][j][k] = INT_MAX;
    f[0][sum[0]][sum[1]] = 0;
    for (int i = 0; i < 6; i++) {
        for (int a = 0; a <= tot; a++) {
            for (int b = 0; b <= tot - a; b++) {
                int c = tot - a - b;
                if (f[i][a][b] == INT_MAX) continue;
                // a -> b, c
                for (int tb = 0; tb <= own[0][i + 1]; tb++) {
                    for (int tc = 0; tc <= own[0][i + 1] - tb; tc++) {
                        if (tb + tc == 0) continue;
                        int _a = a - VAL[i + 1] * (tb + tc);
                        int _b = b + VAL[i + 1] * tb;
                        int _c = c + VAL[i + 1] * tc;
                        f[i + 1][_a][_b] = std::min(f[i + 1][_a][_b], f[i][a][b] + tb + tc);
                    }
                }
                // b -> a, c
                for (int ta = 0; ta <= own[1][i + 1]; ta++) {
                    for (int tc = 0; tc <= own[1][i + 1] - ta; tc++) {
                        if (ta + tc == 0) continue;
                        int _a = a + VAL[i + 1] * ta;
                        int _b = b - VAL[i + 1] * (ta + tc);
                        int _c = c + VAL[i + 1] * tc;
                        f[i + 1][_a][_b] = std::min(f[i + 1][_a][_b], f[i][a][b] + ta + tc);
                    }
                }
                // c -> a, b
                for (int ta = 0; ta <= own[2][i + 1]; ta++) {
                    for (int tb = 0; tb <= own[2][i + 1] - ta; tb++) {
                        if (ta + tb == 0) continue;
                        int _a = a + VAL[i + 1] * ta;
                        int _b = b + VAL[i + 1] * tb;
                        int _c = c - VAL[i + 1] * (ta + tb);
                        f[i + 1][_a][_b] = std::min(f[i + 1][_a][_b], f[i][a][b] + ta + tb);
                    }
                }
                // a, b -> c
                for (int fa = 0; fa <= own[0][i + 1]; fa++) {
                    for (int fb = 0; fb <= own[1][i + 1]; fb++) {
                        if (fa + fb == 0) continue;
                        int _a = a - VAL[i + 1] * fa;
                        int _b = b - VAL[i + 1] * fb;
                        int _c = c + VAL[i + 1] * (fa + fb);
                        f[i + 1][_a][_b] = std::min(f[i + 1][_a][_b], f[i][a][b] + fa + fb);
                    }
                }
                // a, c -> b
                for (int fa = 0; fa <= own[0][i + 1]; fa++) {
                    for (int fc = 0; fc <= own[2][i + 1]; fc++) {
                        if (fa + fc == 0) continue;
                        int _a = a - VAL[i + 1] * fa;
                        int _b = b + VAL[i + 1] * (fa + fc);
                        int _c = c - VAL[i + 1] * fc;
                        f[i + 1][_a][_b] = std::min(f[i + 1][_a][_b], f[i][a][b] + fa + fc);
                    }
                }
                // b, c -> a
                for (int fb = 0; fb <= own[1][i + 1]; fb++) {
                    for (int fc = 0; fc <= own[2][i + 1]; fc++) {
                        if (fb + fc == 0) continue;
                        int _a = a + VAL[i + 1] * (fb + fc);
                        int _b = b - VAL[i + 1] * fb;
                        int _c = c - VAL[i + 1] * fc;
                        f[i + 1][_a][_b] = std::min(f[i + 1][_a][_b], f[i][a][b] + fb + fc);
                    }
                }
                f[i + 1][a][b] = std::min(f[i + 1][a][b], f[i][a][b]);
            }
        }
    }
    int resA = sum[0] - a + c, resB = sum[1] - b + a, resC = sum[2] - c + b;
    if (resA < 0 || resB < 0 || resC < 0 || f[6][resA][resB] == INT_MAX) puts("impossible");
    else printf("%d\n", f[6][resA][resB]);
    return 0;
}

「SHOI2008」循环的债务 - DP

Contents

题解

代码