题意

规则同汉诺塔，强制规定移动操作的优先级，每次选择合法的优先级最高的操作，两次操作不能移动同一个盘子，保证有解，求移动次数

思路

将普通汉诺塔问题的思路用在这道题上面，容易证明\(f\)满足线性递推关系:\(f[i]=k*f[i-1]+b\)，暴力\(dfs\)出前三个\(f\)，就可以求出\(k=\frac{f[3]-f[2]}{f[2]-f[1]},b=f[2]-f[1]*k\)

Code

#include
    
     #define N 35 using namespace std;typedef long long ll;int n;char a[7][3];ll f[N],k,b;int st[4][4],top[4];template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}void dfs(int step,int opt,int las){    if(top[2]==opt||top[3]==opt) {f[opt]=step; return;}    for(int i=1;i<=6;++i)    {        int fr=a[i][0]-'A'+1,to=a[i][1]-'A'+1;        if(!top[fr]) continue;        if(st[fr][top[fr]]==las) continue;        if(top[to]&&st[fr][top[fr]]>st[to][top[to]]) continue;        st[to][++top[to]]=st[fr][top[fr]];        --top[fr];        dfs(step+1,opt,st[to][top[to]]);        break;    }}int main(){    scanf("%d",&n);    for(int i=1;i<=6;++i) scanf("%s",a[i]);    for(int i=1;i<=3;++i) top[i]=0;    st[1][++top[1]]=1;    dfs(0,1,-1);    for(int i=1;i<=3;++i) top[i]=0;    st[1][++top[1]]=2; st[1][++top[1]]=1;    dfs(0,2,-1);    for(int i=1;i<=3;++i) top[i]=0;    st[1][++top[1]]=3; st[1][++top[1]]=2; st[1][++top[1]]=1;    dfs(0,3,-1);    k=(f[3]-f[2])/(f[2]-f[1]);    b=f[2]-f[1]*k;    for(int i=4;i<=n;++i) f[i]=k*f[i-1]+b;    printf("%lld\n",f[n]);    return 0;}