题解 UVA11366 【Circle of Debt】

发表于 更新于 阅读次数： Waline：
UVA11366 【Circle of Debt】题解。

题目大意：

A欠B $ab$ 元，B欠C $bc$ 元，C欠A $ca$ 元。现在告诉你每个人的100元，50元，20元，10元，5元，1元的硬币各有多少个，问你最少需要交换多少张硬币才能还清他们之间的债务。（当$ab$=$bc$=$ca$时就可以认为债务已经还清）无法还清输出$impossible$
每个人最多有30张硬币，他们的总钱数不多与1000元。——FlierKing的课件

这个麻烦管理员顺手搬到题面上。

这题目一看就是搜索

但纯爆搜是肯定要T的

首先是一个基本性的优化：

对于每个币种，只可能有两种情况：

  • 两个人给一个人钱

  • 一个人给两个人钱

那么搜索的复杂度就减少了

然后是两个非常常见的优化：

  • 最优性剪枝：如果当前的答案已经不如已有的答案了，剪枝；

  • 可行性剪枝：我们考虑先搜索面值小的硬币，然后搜索大面值的硬币时，每两个人直接的欠的金额差必须可以被此时剩下面值的硬币的最大公因数整除，不然这两个人之间就永远纠缠不清。

加上这些优化代码AC就没什么问题了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
int t,d[3],ans,cnt,u[3][6],td[3],a[6][4];
const int v[]={100,50,20,10,5,1};//币种数组
bool check(int x,int y){//暴力判可行
	switch(y){
		case 5:return true;
		case 4:return x%5==0;
		case 2:return x%10==0;
		case 1:return x%50==0;
		case 0:return x%100==0;
	}
}
void dfs(int x){
	if(x<0){if(td[0]==td[1]&&td[1]==td[2])ans=min(ans,cnt);return;}//债务还清了，更新答案
	if(cnt>=ans)return;//最优性剪枝
	if(!check(td[0]-td[1],x)||!check(td[1]-td[2],x))return;//可行性剪枝
	for(int i=0;i<3;i++){
		int nex=(i+1)%3,pre=(i+2)%3;
		for(int j=0;j<=u[i][x];j++)
		for(int k=0;k<=u[i][x]-j;k++){
			td[i]-=j*v[x],td[pre]+=k*v[x],cnt+=j+k;
			dfs(x-1);
			cnt-=j+k,td[i]+=j*v[x],td[pre]-=k*v[x];
		}
		for(int j=0;j<=u[nex][x];j++)
		for(int k=0;k<=u[pre][x];k++){
			td[i]+=j*v[x],td[pre]-=k*v[x],cnt+=j+k;
			dfs(x-1);
			cnt-=j+k,td[i]-=j*v[x],td[pre]+=k*v[x];
		}
	}
}
int main(){
	scanf ("%d",&t);
	while(t--){
		ans=inf;
		for(int i=0;i<3;i++)scanf ("%d",&td[i]),d[i]=td[i];
		for(int i=0;i<3;i++)
		for(int j=0;j<6;j++)scanf ("%d",&u[i][j]);
		dfs(5);
		if(ans==inf)puts("impossible");
		else printf("%d\n",ans);
	}
	return 0;
}