省赛选拔赛——组队赛第三场

发表于 分类于 Disqus：

Rank 6。
就出了一道题，是2012年芝加哥大学邀请赛的题，感觉难度不小。
D：HDU 4260
给出汉诺塔当前状态，求移动到B上还需要几步。给出的状态是移动的最优解的中间状态，递归求解，倒着遍历字符串，判断当前完成了多少，用总步数减去已经完成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
using namespace std;
typedef long long LL;
LL a[65];
LL hanoi(char A,char B,char C,string s){
    LL ans=0;
    int cnt=1;
    while(s[(int)s.length()-cnt]==B) ans+=a[(int)s.length()-cnt]+1,++cnt;
    if(cnt>s.length()) return ans;
    if(cnt&1) ans+=hanoi(A,C,B,s.substr(0,s.length()-cnt));
    else ans+=hanoi(C,A,B,s.substr(0,s.length()-cnt));
    return ans;
}
int main(){
    for(int i=1;i<65;++i) a[i]=(a[i-1]<<1)+1;
    string s;
    while(cin>>s&&s!="X")
        cout<<a[s.length()]-hanoi('A','B','C',s)<<endl;
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章