【算法-搜索】POJ3634 circle of debt

由 联环己烷 发布

万万没想到自己害有写题解的一天QAQ……

题目大意

甲乙丙三个人互相之间有债务关系,并且每个人都有若干张纸币,面值为1,5,10,20,50,100,每人纸币不超过30张,债务和每人的钱数都不超过1000,问最少交换几张纸币就能还清债务?

注明:甲欠乙x元,乙欠丙x元,丙欠甲x元,或者乙欠甲x元,丙欠乙x元,甲欠丙x元,这两种情况也算还清债务。

也许我初三的时候有可能做得出来,但现在肯定是做不出来了……

思路

搜索(dfs)+剪枝。

首先想想枚举什么比较好?对于每个人的每种面值钞票分别搜?那肯定会TLE……

其实枚举钞票种类就好了,不难发现,对于一种特定种类的钞票,如果出现甲给乙几张,乙给丙几张,丙给甲几张的环,肯定是不优的,故只可能存在这种类型的钞票,某个人从另外两个人那里收到,或者某个人收到另外两个人给的两种情况,那么枚举部分就很简单了。

最优性剪枝:如果当前答案大于等于已知答案,剪枝。

最优性剪枝的扩展:对当前枚举的是哪种钞票、三个人之间的债务关系进行哈希,如果之前搜到这种状态时搜出了更优解,就剪枝。

可行性剪枝
假设你们只能交换100的钞票,不论怎么交换,三人之间的债务关系除以100的余数都是不可能改变的,于是就可以想到一种可行性剪枝,从小面额钞票往大面额搜,如果债务的余数除以剩下钞票的最大公约数不相同,则剪枝。

常数优化
最慢的操作是取模,如果你单纯地得到余数,由于债务可能有负数,所以需要取模两次得到正的模值。故要么你把第二次取模部分改为加减法操作,要么判断债务的差值与最大公约数的余数是否为0。

备注:哈希确实要时间,我用了map,如果不开O2的话,加哈希在POJ上反而过不了。为什么我还是写了哈希呢?因为我们学校的作业,不用哈希又过不了……
草,搜索好玄学QAQ

代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

#define RI register int

const int inf=0x3f3f3f3f;
int T,ans;
const int v[10]={100,50,20,10,5,1};
int debt[3],money[3][10];
map<long long,int> hash_table;

long long getHash(int x) {//哈希是人类进步的阶梯
    long long re=(debt[0]+1000)*2001LL*10000LL;
    re+=(debt[1]+1000)*10000LL;
    re+=debt[2]+1000LL;
    re=re*10LL+x;return re;
}
int yu(int mon,int x) {
    if(x==0) return mon%100!=0;
    else if(x==1) return mon%50!=0;
    else if(x==2) return mon%10!=0;
    else if(x==3) return mon%10!=0;
    else if(x==4) return mon%5!=0;
    else return 0;
}
void dfs(int x,int cnt) {
       if(cnt>=ans) return;
    if(debt[0]==debt[1]&&debt[1]==debt[2]) {ans=cnt;return;}
    if(x==-1) return;

    long long hashV=getHash(x);
    if(!hash_table.count(hashV)) hash_table[hashV]=cnt;
    else if(hash_table[hashV]>cnt) hash_table[hashV]=cnt;
    else return;

    /*
    无论怎么还,债务除剩下钱币种类的最大公约数的余数不变
    */
    if(yu(debt[0]-debt[1],x)||yu(debt[1]-debt[2],x)) return;

    /*
    由于债务对等也算还完了
    所以对于每种面额的纸币,只可能是一个人还给两个人,或者两个人给同一个人
    如果出现A->B->C这样的还款链,不难发现不如直接改成A->C
    */
    for(RI i=0;i<3;++i) {
        int j=(i+1)%3,k=(i+2)%3;
        for(RI to_j=0;to_j<=money[i][x];++to_j)
            for(RI to_k=0;to_k+to_j<=money[i][x];++to_k) {
                debt[i]-=to_j*v[x],debt[k]+=to_k*v[x];
                dfs(x-1,cnt+to_j+to_k);
                debt[i]+=to_j*v[x],debt[k]-=to_k*v[x];
            }
        for(RI from_j=0;from_j<=money[j][x];++from_j)
            for(RI from_k=0;from_k<=money[k][x];++from_k) {
                debt[i]+=from_j*v[x],debt[k]-=from_k*v[x];
                dfs(x-1,cnt+from_j+from_k);
                debt[i]-=from_j*v[x],debt[k]+=from_k*v[x];
            }
    }
}

int main()
{
    scanf("%d",&T);
    while(T--) {
        for(RI i=0;i<3;++i) scanf("%d",&debt[i]);
        for(RI i=0;i<3;++i)
            for(RI j=0;j<=5;++j) scanf("%d",&money[i][j]);
        hash_table.clear();
        ans=inf,dfs(5,0);
        if(ans==inf) puts("impossible");
        else printf("%d\n",ans);
    }
    return 0;
}

暂无评论

发表评论


京公网安备 11010802033049号