题目地址：洛谷：【P4026】[SHOI2008]循环的债务 – 洛谷、BZOJ：Problem 1021. — [SHOI2008]Debt 循环的债务

题目描述

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块给C，此时只有5张钞票被交换过。
没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。

题意简述

有三个人，有六种可以用来支付的钞票，面值分别为$100, 50, 20, 10, 5, 1$，他们互相有一些欠钱关系，1欠2的钱为$x_1$，2欠3的钱为$x_2$，3欠1的钱为$x_3$，现在给你每个人拥有的6种钞票数量，求最少的钞票交换次数，使得互相欠的钱可以被还清。

输入输出格式

输入格式：
输入的第一行包括三个整数：x1、x2、x3（-1,000≤x1，x2，x3≤1,000），其中x1代表Alice欠Bob的钱（如果x1是负数，说明Bob欠了Alice的钱），x2代表Bob欠Cynthia的钱（如果x2是负数，说明Cynthia欠了Bob的钱），x3代表Cynthia欠Alice的钱（如果x3是负数，说明Alice欠了Cynthia的钱）
接下来有三行，每行包括6个自然数：
a100，a50，a20，a10，a5，a1
b100，b50，b20，b10，b5，b1
c100，c50，c20，c10，c5，c1
a100表示Alice拥有的100元钞票张数，b50表示Bob拥有的50元钞票张数，以此类推。
另外，我们保证有a10+a5+a1≤30，b10+b5+b1≤30，c10+c5+c1≤30，而且三人总共拥有的钞票面值总额不会超过1,000。

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

输入输出样例

输入样例#1：

10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0

输出样例#1：

5

输入样例#2：

-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

输出样例#2：

0

说明

对于100%的数据，x1、x2、x3 ≤ |1,000|。

题解

数据范围非常动态规划。我们设计这样的状态，$dp[i][s1][s2]$表示只考虑前$i$种钞票，第一个人当前所持金额为$s1$，第二个为$s2$，第三个人可以通过总金额减去前两个人的金额算出。我们枚举前两个人第$i$种钞票在交换后有多少，然后计算每个人的该种钞票数量差值绝对值之和的一半，即为从原来状态到当前状态第$i$种钞票的最小交换次数。最后判断互不相欠的情况下是否有人金额为负数以及该情况是否可达就好。
不过似乎，BZOJ的1s时限这种方法过不去。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline int min(int a, int b) {
    return a < b ? a : b;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1005, INF = 0x3f3f3f3f;
const int par[] = {0, 100, 50, 20, 10, 5, 1};

int x1, x2, x3, a[4][7], dp[2][MAXN][MAXN], cnt[7], sum[4];

int main() {
    x1 = readint(); x2 = readint(); x3 = readint();
    for(register int i = 1; i <= 3; i++) {
        for(register int j = 1; j <= 6; j++) {
            a[i][j] = readint();
            cnt[j] += a[i][j];
            sum[i] += a[i][j] * par[j];
        }
    }
    int l1 = sum[1] + x3 - x1, l2 = sum[2] + x1 - x2, l3 = sum[3] + x2 - x3;
    if(l1 < 0 || l2 < 0 || l3 < 0) {
        puts("impossible"); return 0;
    }
    sum[0] = sum[1] + sum[2] + sum[3];
    for(register int i = 0; i <= sum[0]; i++) {
        memset(dp[0][i], 0x3f, sizeof(int) * (sum[0] + 2));
    }
    dp[0][sum[1]][sum[2]] = 0;
    int now = 1, s3, c3, ns1, ns2, ns3;
    for(register int i = 1; i <= 6; i++) {
        for(register int i = 0; i <= sum[0]; i++) {
            memset(dp[now][i], 0x3f, sizeof(int) * (sum[0] + 2));
        }
        for(register int s1 = 0; s1 <= sum[0]; s1++) {
            for(register int s2 = 0; s1 + s2 <= sum[0]; s2++) {
                s3 = sum[0] - s1 - s2;
                if(dp[now ^ 1][s1][s2] >= INF) continue;
                dp[now][s1][s2] = min(dp[now][s1][s2], dp[now ^ 1][s1][s2]);
                for(register int c1 = 0; c1 <= cnt[i]; c1++) {
                    for(register int c2 = 0; c1 + c2 <= cnt[i]; c2++) {
                        c3 = cnt[i] - c1 - c2;
                        ns1 = s1 + (c1 - a[1][i]) * par[i];
                        ns2 = s2 + (c2 - a[2][i]) * par[i];
                        ns3 = s3 + (c3 - a[3][i]) * par[i];
                        if(ns1 < 0 || ns2 < 0 || ns3 < 0) continue;
                        dp[now][ns1][ns2] = min(dp[now][ns1][ns2],
                            dp[now ^ 1][s1][s2] + (abs(c1 - a[1][i]) + abs(c2 - a[2][i]) 
                            + abs(c3 - a[3][i])) / 2);
                    }
                }
            }
        }
        now ^= 1;
    }
    if(dp[now ^ 1][l1][l2] >= INF) {
        puts("impossible");
    } else {
        printf("%d", dp[now ^ 1][l1][l2]);
    }
    return 0;
}