【bzoj1021】[SHOI2008]Debt 循环的债务

2015.04.25 14:06 Sat | 2次阅读 | 旧日oi | 固定链接 | 源码

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
输入二
-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Sample Output

输出一
5
输出二
0

HINT

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

题解

这么简单的dp怎么就是想不到呢……还傻逼的建网络流图……
dp[i][j][k]表示用前i种货币进行交换,A有j元,B有k元的最小交换次数
我们发现,每张货币只有一次流通是有效的,所以交换一共只有6种情况,A  TO BC     B TO AC       C TO AB      AB TO C       AC TO B         BC TO A
然后分别转移就好了……
另外可以用剩余货币的最大公约数来剪枝一下,如果(目标钱数-j)能整除剩余的面值的最大公约数,那么显然这个j就没有意义了。

我的程序

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int x1,x2,x3,sa,sb,sc,sum,ea,eb,ec;
int a[7],b[7],c[7];
int money[7]={0,1,5,10,20,50,100};
int dp[2][1005][1005];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    cin>>x1>>x2>>x3;
    for(int i=6;i;i--)
        cin>>a[i],sa+=money[i]*a[i];
    for(int i=6;i;i--)
        cin>>b[i],sb+=money[i]*b[i];
    for(int i=6;i;i--)
        cin>>c[i],sc+=money[i]*c[i];
    ea=sa-x1+x3;eb=sb+x1-x2;ec=sc+x2-x3;sum=sa+sb+sc;
    memset(dp,0x3f,sizeof(dp));dp[0][sa][sb]=0;
    for(int now=1,pre=0,i=1;i<=6;i++,now^=1,pre^=1)
    {
        for(int j=0;j<=sum;j++)
        for(int k=0;k<=sum;k++)
        dp[now][j][k]=dp[pre][j][k];
        int g=money[i],x,y;
        for(int j=i+1;j<=6;j++) g=gcd(g,money[j]);
        for(x=0;(ea-x)%g;x++);for(y=0;(eb-y)%g;y++);
        if((ec-(sum-x-y))%g) continue;
        for(int j=x;j+y<=sum;j+=g)
        for(int k=y;j+k<=sum;k+=g)
        if(dp[pre][j][k]!=inf)
        {
            for(int p=0;p<=a[i];p++)
            for(int r=0;r<=p;r++)
            dp[now][j-p*money[i]][k+r*money[i]]=min(dp[now][j-p*money[i]][k+r*money[i]],dp[pre][j][k]+p);
            for(int p=0;p<=b[i];p++)
            for(int r=0;r<=p;r++)
            dp[now][j+r*money[i]][k-p*money[i]]=min(dp[now][j+r*money[i]][k-p*money[i]],dp[pre][j][k]+p);
            for(int p=0;p<=c[i];p++)
            for(int r=0;r<=p;r++)
            dp[now][j+r*money[i]][k+(p-r)*money[i]]=min(dp[now][j+r*money[i]][k+(p-r)*money[i]],dp[pre][j][k]+p);
            for(int p=0;p<=a[i];p++)
            for(int r=0;r<=b[i];r++)
            dp[now][j-p*money[i]][k-r*money[i]]=min(dp[now][j-p*money[i]][k-r*money[i]],dp[pre][j][k]+r+p);
            for(int p=0;p<=a[i];p++)
            for(int r=0;r<=c[i];r++)
            dp[now][j-p*money[i]][k+(p+r)*money[i]]=min(dp[now][j-p*money[i]][k+(p+r)*money[i]],dp[pre][j][k]+r+p);
            for(int p=0;p<=b[i];p++)
            for(int r=0;r<=c[i];r++)
            dp[now][j+(p+r)*money[i]][k-p*money[i]]=min(dp[now][j+(p+r)*money[i]][k-p*money[i]],dp[pre][j][k]+r+p);
        }
    }
    if(dp[0][ea][eb]==inf) puts("impossible");
    else cout<<dp[0][ea][eb]<<endl;
}```