当前位置: 代码迷 >> 综合 >> UVA 10795 A Different Task 汉诺塔加强版 *
  详细解决方案

UVA 10795 A Different Task 汉诺塔加强版 *

热度:36   发布时间:2023-09-23 05:47:24.0

题目地址:http://vjudge.net/problem/UVA-10795

参考自刘汝佳的思路


以下是个人理解:

普通的汉诺塔肯定都做过了,就是把一叠碟子放到另一根上

看到这个问题就很自然地想到普通的汉诺塔问题,于是也便想怎么转化成普通的汉诺塔问题:一堆放在另一堆上,需要2^(n-1)-1步

那么是不是可以定义一种中间状态,并且这个中间状态可以运用到普通汉诺塔,那么答案就是start->中间状态+final->中间状态

这个中间状态就是需要排的编号最大的盘子k,k要放到final柱子上,那么其他1~k-1盘子只能在除了k和final柱子的另一根记为other上

于是就需要算出start和final局面1~k-1盘子到other这柱子上的步骤,因为other这根柱子上排序是1~k-1的就像普通的汉诺塔一样,所以可以直接用结论2^(n-1)-1


另外,因为编号小的不能放在编号大的下面,所以我们应该从编号大的先开始排,那么排好后就不需要再考虑这个盘子了。比如,同时在拍k盘子时,比k大的肯定都放好了,他们也并不碍事,所以可以无视他们


#include <bits/stdc++.h>
using namespace std;
const int maxn=60+3;
typedef long long LL;
int start[maxn],final[maxn];
LL f(int* P,int i,int final){if(i==0) return 0;if(P[i]==final) return f(P,i-1,final); //i在final柱子上,不用排else return f(P,i-1,6-final-P[i])+(1LL<<(i-1)); //1~i-1到final需要2^(i-1)-1,加上移动i的步数
}
int main(int argc, char const *argv[])
{int n,kase=0;while(scanf("%d",&n)==1&&n){for(int i=1;i<=n;i++) scanf("%d",&start[i]);for(int i=1;i<=n;i++) scanf("%d",&final[i]);int k=n;while(k>=1&&final[k]==start[k]) k--;  //找不同柱子编号最大的一个LL ans=0;if(k>=1){int other=6-start[k]-final[k];ans=f(start,k-1,other)+f(final,k-1,other)+1;}printf("Case %d: %lld\n", ++kase,ans);}return 0;
}




  相关解决方案