2285 - 【宽搜入门】巧妙取量
时间限制 : 2 秒
内存限制 : 128 MB
【题目描述】
有三个容器，容量分别为 a,b,c（a> b > c ),一开始a装满油，现在问是否只靠abc三个容器量出k升油。如果能就输出“yes”，并且说明最少倒几次，否则输出“no”。例如：10升油在10升的容器中，另有两个7升和3升的空容器，要求用这三个容器倒油，使得最后在abc三个容器中有一个刚好存有5升油，问最少的倒油次数是多少？（每次倒油，A容器倒到B容器，或者A内的油倒完，或者B容器倒满。
10 7 3
（10 0 0）
（3 7 0）:第一次
（3 4 3）：第二次
（6 4 0）：第三次
（6 1 3）：第四次
（9 1 0）：第五次
（9 0 1）：第六次
（2 7 1）：第七次
（2 5 3）：第八次，出现5了。
Input
【输入格式】
有多组测试数据。
输入a，b，c, k四个正整数( 100 ≥ a > b > c≥1 , 1≤k< 100 )
Output
【输出格式】
如果能得到k就输出两行。
第一行“yes”，第二行为最少的次数
否则输出“no”
Sample Input
10 7 3 5
Sample Output
yes
8
题目输入
题目输出
输入/输出样例
输入格式
输出格式
C++解答
#include<cstdio> #include<cstring> using namespace std; struct node{int a[4],dep;}list[41000]; int nn[4],n,ed,head,tail; bool myhash[41000]; int Fkangtuo(node tno) { return tno.a[1]*101+tno.a[2]*102+tno.a[3]; } bool OK(node tno) { if(tno.a[1]==n||tno.a[2]==n||tno.a[3]==n) return true; return false; } node dao(int x,int y) { node tno=list[head]; int zz=tno.a[x]+tno.a[y]; if(zz>nn[y]) { tno.a[y]=nn[y]; tno.a[x]=zz-nn[y]; } else {tno.a[y]=zz;tno.a[x]=0;} tno.dep++; return tno; } int main() { bool bo; while(scanf("%d%d%d%d",&nn[1],&nn[2],&nn[3],&n)!=EOF) { bo=false; memset(myhash,false,sizeof(myhash)); if(nn[1]==n) {printf("yes\n0\n");continue;} list[1].a[1]=nn[1];list[1].a[2]=list[1].a[3]=0; myhash[Fkangtuo(list[1])]=true; head=tail=1; while(head<=tail) { node tno; for(int i=1;i<=3;i++) { if(!bo) for(int k=1;k<=3;k++) if(i!=k) { tno=dao(i,k); int x=Fkangtuo(tno); if(!myhash[x]) { myhash[x]=true; list[++tail]=tno; if(OK(tno)) { bo=true; printf("yes\n%d\n",list[tail].dep); break; } } } } head++; } if(!bo) printf("no\n"); } }