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

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博客 ,格式可能有所偏差。