更好的阅读体验

具体思路

设 $f_{i,x}$ 表示 $i$ 个盘子从 $x$ 柱子出发的步数。

设 $g_{i,x}$ 表示 $i$ 个盘子从 $x$ 柱子出发到哪个柱子。

记 $y=g_{i-1,x}$，$z=6-x-y$。

其中，$y$ 代表将前 $i-1$ 个盘子从 $x$ 柱子移到的柱子，$z$ 代表剩下的那个柱子。

分类讨论。

• 若 $g_{i-1,y}=z$，表示 $i-1$ 个盘子先从 $x$ 移到 $y$，第 $i$ 个盘子从 $x$ 移到 $z$，$i-1$ 个盘子再从 $y$ 移回 $z$。

$f_{i,x}=f_{i-1,x}+1+f_{i-1,y},g_{i,x}=z$。

• 若 $g_{i-1,y}=x$，表示 $i-1$ 个盘子先从 $x$ 移到 $y$，第 $i$ 个盘子从 $x$ 移到 $z$，$i-1$ 个盘子再从 $y$ 移回 $x$，第 $i$ 个盘子从 $z$ 移到 $y$，$i-1$ 个盘子再从 $x$ 移回 $y$。

$f_{i,x}=f_{i-1,x}+1+f_{i-1,y}+1+f_{i-1,x},g_{i,x}=y$。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=31,M=4;
int g[N][M],vis[M];LL f[N][M];
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=6;i++){
		char op[10];scanf("%s",op+1);
		int x=op[1]-'A'+1,y=op[2]-'A'+1;
		if(vis[x])continue;
		vis[x]=1;
		f[1][x]=1,g[1][x]=y;
	}
	for(int i=2;i<=n;i++){
		for(int x=1;x<=3;x++){
			int y=g[i-1][x],z=6-x-y;
			if(g[i-1][y]==z){
				f[i][x]=f[i-1][x]+1+f[i-1][y];
				g[i][x]=z;
			}
			if(g[i-1][y]==x){
				f[i][x]=f[i-1][x]+1+f[i-1][y]+1+f[i-1][x];
				g[i][x]=y;
			}
		}
	}
	printf("%lld\n",f[n][1]);
	return 0;
}

#include<stdio.h>
#include<math.h>
typedef long long ll;
char a[4];
int s[9],p,n,i=6;
ll f(int x){
	if(x==1)return (ll)2*pow(3,n-1)-1;
	if(x)return (ll)pow(2,n)-1;
	return (ll)pow(3,n-1);
}
int main(){
	scanf("%d",&n);
	while(i--)scanf("%s",a),s[(a[0]-'A')*3+a[1]-'A']=i;
	if(s[1]>s[2]){
		if(s[5]<s[3])p=1;
		else if(s[6]>s[7])p=2;
	}else if(s[7]<s[6])p=1;
	else if(s[3]>s[5])p=2;
	printf("%lld",f(p));
	return 0;
}

分析

首先，如果不按照题目中的限制来，那么最优操作步数为 $h_n=2\times h_{n-1}+1$，其中 $h_1=1$。

大胆猜测这道题的答案也满足一个 $h'_n=k\times h'_{n-1}+b$ 的递推关系。

模拟出前三项，计算出 $k$ 和 $b$ 最后递推即可。

实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#define LL long long

using namespace std;

int n, f[10], t[10];
LL ans[50];
stack<int> st[5];

int simulate(int n) {
  for (int i = 1; i <= 3; i++)
    while (!st[i].empty()) st[i].pop();
  for (int i = n; i >= 1; i--) st[1].push(i);
  int ans = 0, l = 0;
  while (true) {
    ans++;
    for (int i = 1; i <= 6; i++)
      if (!st[f[i]].empty() && st[f[i]].top() != l &&
          (st[t[i]].empty() || st[f[i]].top() < st[t[i]].top())) {
        l = st[f[i]].top(), st[f[i]].pop(), st[t[i]].push(l);
        break;
      }
    for (int i = 1; i <= 3; i++)
      if (st[i].size() == n) return ans;
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= 6; i++) {
    char x, y;
    cin >> x >> y;
    f[i] = x - 'A' + 1, t[i] = y - 'A' + 1;
  }
  ans[1] = simulate(1), ans[2] = simulate(2), ans[3] = simulate(3);
  int k = (ans[3] - ans[2]) / (ans[2] - ans[1]), b = ans[2] - ans[1] * k;
  for (int i = 4; i <= n; i++) ans[i] = ans[i - 1] * k + b;
  return cout << ans[n] << endl, 0;
}