#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int n,step=0;
int a[50];
bool ok=1;

void mov(int n,int from,int to,int temp)
{   

    if(!ok || n<=0) return;
    if(a[n]==from)
    {
        mov(n-1,from,temp,to);
    }
    else if(a[n]==to)
    {
        step+=pow(2,n-1);
        mov(n-1,temp,to,from);
    }
    else if(a[n]==temp)
    {   
        ok=0;
        return;
    }
    //cout<<n<<" "<<from<<" "<<to<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    mov(n,1,2,3);
    if(ok)
      cout<<step;
    else
      cout<<"-1"; 
    return 0;
}

首先地球人都知道n个盘子问题的移动数是2的n次方-1。

先来看3个盘的时候（题目上面有）。

我们发现第3个盘只移动了一次（从1到2），因此如果发现它在3号柱上直接输出-1。

方案是：

1-2盘开始在1号柱上，把1-2盘移到3号柱上。

把3盘移到2号柱。

1-2盘开始在3号柱上，把1-2盘移到2号柱上。

我们发现，3盘的位置决定了1-2盘开始在什么地方，和要去哪里！！

如果3盘在1，那么解数不变，而1-2盘开始在1号柱，要去3号柱（子问题）

如果3盘在2，那么说明1-2已经到3号柱上去了（ans相应增加），而现在1-2盘需要从3号柱到2号柱（又是一个子问题）

至此，我们已经成功的转化出了子问题。

Dfs(n,st,ed)表示前n个盘，需要从st号柱到ed柱去，然后根据盘n的状态可以转化出子问题。

procedure dfs(k,a,b:longint);

begin

if k=0 then exit;

if s[k]=b then

begin

m:=m+two[k-1];

dfs(k-1,6-a-b,b);

end else

if s[k]=a then dfs(k-1,a,6-a-b)

else

begin

writeln(-1);

halt;

end;

end;

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n;
int f[35];
int a[40];
ll hanoi(int n) {
    if (n<=0) return 0;
    if (f[n]) return f[n];
    ll res=0;
    res+=hanoi(n-1);
    ++res;
    res+=hanoi(n-1);
    f[n]=res;
    return res;
}
ll work(int n,int from,int to,int temp) {
    if (n<=0) return 0;
    if (a[n]==temp) {
        cout<<-1<<endl;
        exit(0);
    }
    if (a[n]==from) {
        return work(n-1,from,temp,to);
    }
    ll res=0;
    res+=f[n-1]+1;
    if (a[n]==to) {
        bool flag=1;
        FOR(i,n-1) if (a[i]!=temp) {
            flag=0;
            break;
        }
        if (flag) {
            return res;
        }
    }
    return res+work(n-1,temp,to,from);
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    FOR(i,n) cin>>a[i];
    hanoi(n);
    cout<<work(n,1,2,3)<<endl;
    return 0;
}

var n,x,y,z,i:longint; //x起点柱 y终点柱 z中转柱
a:array[1..31] of longint;
ans:int64;
begin
readln(n);
for i:=1 to n do read(a[i]);
readln;
ans:=0;
x:=1;
y:=2;
z:=3;
for i:=n downto 1 do begin
if a[i]=z then begin
writeln(-1);
exit;
end;
if a[i]=x then begin
y:=z;
z:=6-x-y;
end else begin
ans:=ans+1 shl(i-1);
x:=z;
z:=6-x-y;
end;
end;
writeln(ans);
end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

n,i:integer;

p:array[1..31]of integer;

f:array[1..31]of qword;

ans:qword;

procedure work(k,a,b,c:integer);

begin

if p[k]=c then

begin writeln(-1);halt;end;

if k=1 then

begin if p[k]=b then inc(ans);end

else

if p[k]=a then work(k-1,a,c,b)

else begin

inc(ans,f[k-1]+1);

work(k-1,c,b,a);

end;

end;

begin

readln(n);

for i:=1 to n do read(p[i]);

f[1]:=2;

for i:=2 to n do

begin

f[i]:=f*2;

dec(f);

end; //f[i]=2^i-1

work(n,1,2,3);

writeln(ans);

end.

12:58 2009-2-20

推..

lx两人均正解...

多谢fammiebright牛写的题解,

让我2次AC,

第一次O(2^n)

第二次O(n)(或者大些?O(n^2)?)

天壤之别啊!

对于每一个a[n],

等于to_就加上2^(n-1),

执行后半步;

等于from就直接执行前半步;

等于temp直接输-1;

题目中的代码今天才弄懂,不易啊~

正如题目所给的那个hanoi代码，递归每一次都分“前半步” (hanoi(n-1,from,temp,to_));和“后半步” (hanoi(n-1,temp,to_,from))。这样有了一个状态，就可以判断它处在“前半步”还是“后半步”，再作出相应的递归。

（供大牛们BS）http://dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!343.entry

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

没发现还有个-1的问题，害我找了n次错。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

看错了

以为要把所有的盘移到3号柱子

结果是2号

wa了N次

没看见-1,Wa了N次..

O(3 * n)......

找规律......

开始没用int64,结果90分.....

WA了一个点......

终于通过一百人以下的题了！

gf-sky,gf-fly,gf-star,gbf,ttt

递归.

时间复杂度为O(n)

超级郁闷，一开始只开到31，结果WA掉2个点....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

跟1084比较类似，只是不需要高精度。。。

我的方法。。。

O（n）。。。N=31。。。。

所以，结果是。。。常数时间。。

用了一个极其猥琐的枚举判断无解的方法过了

总体思想是二分

规定要求不能贴出任何有关于此题的程序代码

ft还是删了吧