记搜好题
预处理题目给出了将一个盘从x移到y的代价（代码中为a[][]），当我们知道这并不是最优的
就像最短路floyd一样松弛操作预处理得到两柱之间最优值b[][]
for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) scanf("%lld",&a[i][j]),b[i][j]=a[i][j]; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(i!=j) for(int k=1;k<=3;k++) if(k!=i&&k!=j) b[i][j]=min(b[i][j],b[i][k]+b[k][j]); 记搜主体冷静分析，每次搬n个盘子都有两种搬法：
方法一
方法二
我们知道每次最大盘的代价直接就是a[][]，而其余n-1个是可以由递归记搜得到的
当递归到只剩一个盘时，只需要用预处理出的最优解b[][]即可
int dfs(int l,int r,int n){ if(f[l][r][n]) return f[l][r][n]; //已经走过，直接返回 if(n==1) return b[l][r]; //递归边界，只剩一个盘 int x=6-l-r; //表示中介盘，因为三个盘编号之和为6 int an1=dfs(l,x,n-1)+dfs(x,r,n-1)+a[l][r]; //方法一 int an2=(dfs(l,r,n-1)<<1)+dfs(r,l,n-1)+a[l][x]+a[x][r]; //方法二 return f[l][r][n]=min(an1,an2); //取个最优值 }dfs(l,r,n)表示将n个盘从l移到r的方案数
所以答案就是dfs(1,3,n)
注意这题还会爆int
AC代码：
#include <bits/stdc++.h> #define int long long using namespace std; int n,a[5][5],b[5][5],f[5][5][50]; int dfs(int l,int r,int n){ if(f[l][r][n]) return f[l][r][n]; if(n==1) return b[l][r]; int x=6-l-r; int an1=dfs(l,x,n-1)+dfs(x,r,n-1)+a[l][r]; int an2=(dfs(l,r,n-1)<<1)+dfs(r,l,n-1)+a[l][x]+a[x][r]; return f[l][r][n]=min(an1,an2); } signed main(){ for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) scanf("%lld",&a[i][j]),b[i][j]=a[i][j]; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(i!=j) for(int k=1;k<=3;k++) if(k!=i&&k!=j) b[i][j]=min(b[i][j],b[i][k]+b[k][j]); scanf("%lld",&n); printf("%lld",dfs(1,3,n)); }