题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1019递推。对于汉诺塔问题，存在f[i]=A*f[i-1]+B。
因此只要暴力出f[3]，f[4]，f[5]就能算出A和B，之后递推即可。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MaxN=31;
int n;
long long A,B;
long long f[MaxN];
int now[3][MaxN];
int tot[3];
int can[6][2];
long long dfs(int n,long long ans,int last)
{
//cout<<ans<<endl;
/**//*for (int i=0;i<3;i++)
{
cout<<tot[i]<<' ';
for (int j=0;j<tot[i];j++)
{
cout<<now[i][j]<<' ';
}
cout<<endl;
}*/
if (tot[1]==n || tot[2]==n)
{
return ans;
}
int i;
for (i=0;i<6;i++)
{
if (can[i][0]==last)
{
continue;
}
if (tot[can[i][0]]!=0 && ((now[can[i][0]][tot[can[i][0]]-1]<=now[can[i][1]][tot[can[i][1]]-1] && tot[can[i][1]]!=0) || tot[can[i][1]]==0))
{
//cout<<i<<endl;
now[can[i][1]][tot[can[i][1]]]=now[can[i][0]][tot[can[i][0]]-1];
tot[can[i][0]]--;
tot[can[i][1]]++;
break;
}
}
//system("pause");
return dfs(n,ans+1,can[i][1]);
}
int main()
{
scanf(" %d",&n);
for (int i=0;i<6;i++)
{
char c[5];
scanf(" %s",&c);
can[i][0]=c[0]-'A';
can[i][1]=c[1]-'A';
}
for (int i=1;i<=min(n,5);i++)
{
memset(tot,0,sizeof(tot));
memset(now,0,sizeof(now));
tot[0]=n;
for (int j=0;j<tot[0];j++)
{
now[0][j]=n-j;
}
f[i]=dfs(i,0ll,3);
}
if (n>5)
{
A=(long long)((double)(f[5]-f[4]))/((double)(f[4]-f[3]));
B=f[4]-A*f[3];
for (int i=6;i<=n;i++)
{
f[i]=A*f[i-1]+B;
}
}
printf("%lld\n",f[n]);
return 0;
}