可以通过另一个数组 来改变dp的方向

 

/**************************************************************    Problem: 1019    User: lxy8584099    Language: C++    Result: Accepted    Time:0 ms    Memory:852 kb****************************************************************/ /*    普通的汉诺塔 f[i]=2*f[i-1] + 1     但是这个有明确的方向性     我们设 g[x][i]为 x移动i个到g[x][i] 上面             f[x][i] 为x移动i个到g[x][i] 上面     令g[x][i-1]==y  那么最后一个盘子移动到 z=6-x-y;    如果g[y][i-1]==z  正好可以直接移动过去         f[x][i]=f[x][i-1]+1+f[y][i-1]    如果g[y][i-1]==x  最终就一定是全部在y上         因为当i-1全部移动到x上后 不能移动最小的盘子         只能移动位于z上的最大那个盘子到y         f[x][i]=f[x][i-1]+1+f[y][i-1]+1+f[x][i-1]    对于g数组  根据题目给出的优先级初始化 g[i][1] 的情况    之后的g就是在dp转换中更新  没有更新到的就是不合法情况    dp就只能沿着我们更新过g的路线走下去 */#include
     
      #define ll long longusing namespace std;const int N=50;ll f[N][N];int g[N][N],n,u[N],v[N];char str[10];int main(){    scanf("%d",&n);    for(int i=1;i<=6;i++)    {        scanf("%s",str); u[i]=str[0]-'A'+1; v[i]=str[1]-'A'+1;    }    for(int i=6;i>=1;i--) g[u[i]][1]=v[i];     // 倒着循环 前面的可以覆盖后面的     for(int i=1;i<=3;i++) f[i][1]=1;    for(int i=2;i<=n;i++)    {        for(int x=1;x<=3;x++) // 枚举移动哪一个上面的盘子         {            int y=g[x][i-1],z=6-x-y;            if(g[y][i-1]==z)             {                f[x][i]=f[x][i-1]+1+f[y][i-1];                g[x][i]=z; // 全部移动到了 z             }            else if(g[y][i-1]==x)            {                 f[x][i]=f[x][i-1]+1+f[y][i-1]+1+f[x][i-1];                g[x][i]=y; // 全部移动到了 y             }            else continue; // 剩下的就是不合法情况          }    }    printf("%lld\n",f[1][n]);    return 0;}