CSP-2020倒计时：36天
【SHOI2008】JZOJ2020年9月5日提高组 循环的债务
题目
Description
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张钞票被交换过。
没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。
Input
输入的第一行包括三个整数：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。
Output
如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。
Sample Input
10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0
Sample Output
5
Hint
对于100%的数据，x1、x2、x3 ≤ |1,000|。
题解
注明：以下的\(A\)表示\(Alice\)，\(B\)表示\(Bob\)，\(C\)表示\(Cynthia\)
发现钱的总量是不变的
思考\(DP\)
设\(f[i][j][k]\)表示考虑了前\(i\)种币值（从大到小），\(A\)有\(j\)元，\(B\)有\(k\)元
因为钱的总数不变，那么就可以算出\(C\)的钱
既然总数不变，那么就可以枚举第\(i\)种钱经过交换后\(A\)有多少，\(B\)有多少，算出\(C\)有多少，计算一下交换次数，转移即可
Code
#include<bits/stdc++.h>
using namespace std;
int x1,x2,x3,all,c1,c2,c3,z,tot,now,f[10][1005][1005],cost[7]={0,100,50,20,10,5,1},a[5][10];
int read()
{
int res=0,fh=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') fh=-1,ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
return res*fh;
}
int main()
{
x1=read();x2=read();x3=read();
for (int i=1;i<=3;++i)
for (int j=1;j<=6;++j)
{
a[i][j]=read();
all+=a[i][j]*cost[j];
}
for (int i=1;i<=6;++i)
c1+=a[1][i]*cost[i],c2+=a[2][i]*cost[i];
if (c1-x1+x3>all||c2-x2+x1>all||all-c1-c2-x3+x2>all)
{
printf("impossible\n");
return 0;
}
memset(f,0X3f3f3f,sizeof(f));
f[0][c1][c2]=0;
for (int i=1;i<=6;++i)
for (int j=0;j<=all;++j)
for (int k=0;j+k<=all;++k)
{
if (f[i-1][j][k]>1e9) continue;
tot=a[1][i]+a[2][i]+a[3][i];
for (int x=0;x<=tot;++x)
for (int y=0;y+x<=tot;++y)
{
z=tot-x-y;
now=(abs(a[1][i]-x)+abs(a[2][i]-y)+abs(a[3][i]-z))/2;
if (j-(a[1][i]-x)*cost[i]+k-(a[2][i]-y)*cost[i]>all) continue;
if (j-(a[1][i]-x)*cost[i]<0||k-(a[2][i]-y)*cost[i]<0) continue;
f[i][j-(a[1][i]-x)*cost[i]][k-(a[2][i]-y)*cost[i]]=min(f[i][j-(a[1][i]-x)*cost[i]][k-(a[2][i]-y)*cost[i]],f[i-1][j][k]+now);
}
}
if (f[6][c1-x1+x3][c2-x2+x1]>1e9)
{
printf("impossible\n");
return 0;
}
printf("%d\n",f[6][c1-x1+x3][c2-x2+x1]);
return 0;
}