题意:给定当前汉诺塔的状态,问还有多少步走完,不合法输出“No”。
思路:显然可以一层一层试探下去的。我们设三个柱子为“起始”,“中转”,“终点”,当前状态的最大的盘子不可能在中转站处;如果在起始站,我们需要把其他的移到中转站,然后把最大移到终点。如果在终点站,我们需要把其他的从中转站移到终点站。 每一层减少一个盘子,递推下去就ok了。当时想到了思路,但是没有想到简洁的写法。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans;
bool solve(int num,vector<int>&A,vector<int>&B,vector<int>&C)
{
if(!num) return true;
if(A.size()&&A[]==num){
ans+=(1LL<<((ll)num-));
A.erase(A.begin());
return solve(num-,A,C,B);
}
if(C.size()&&C[]==num){
C.erase(C.begin());
return solve(num-,B,A,C);
}
return false;
}
vector<int>A,B,C;
int main()
{
int La,Lb,Lc,i,j,x;
scanf("%d",&La); for(i=;i<=La;i++) scanf("%d",&x),A.push_back(x);
scanf("%d",&Lb); for(i=;i<=Lb;i++) scanf("%d",&x),B.push_back(x);
scanf("%d",&Lc); for(i=;i<=Lc;i++) scanf("%d",&x),C.push_back(x);
if(!solve(La+Lb+Lc,A,B,C)) puts("No");
else printf("%I64d\n",ans);
return ;
}