河内塔是一个众所周知的数学难题。它由三根杆和一些可以滑动到任何杆上的不同尺寸的圆盘组成。难题从一个整齐的杆中开始，按照尺寸从小到大的顺序排列，最小的位于顶部，从而形成一个圆锥形状。难题的目标是将整个杆移动到另一个杆，遵循以下简单规则：
有了三个圆盘，这个难题可以通过七个步骤解决。解决河内难题所需的最小移动次数是2^n - 1，其中n是圆盘的数量。 SmallY的难题非常类似于着名的河内塔。在河内之谜游戏中，你需要以最少的动作来解决难题，在SmallY的谜题中，每一个动作都需要花费一些钱，而且你需要解决同样的难题，但要花费最少。 在SmallY的难题开始时，所有的n个磁盘都在第一根杆上。将圆盘从杆i移动到杆j需要花费t[i,j]个金钱单位。（1 <= i，j <= 3）.这个难题的目标是将所有的圆盘移动到第三个杆上。在这个问题中给出矩阵t和整数n。您需要计算解决SmallY难题的最小成本，其中包含n个圆盘。 输入输出格式输入格式：前三行中的每一行都包含三个整数 - 矩阵t。第i行第j个整数为t[i,j]（1 <= t[ij] <= 10000; i≠j ）。以下行包含一个整数n表示圆盘数量（1 <= n <= 40)。当i满足: （1 <= i <= 3）, t[i,i] = 0. 输出格式：打印一个整数 - 解决SmallY难题的最低成本。
sol：dp[i][j][k]表示i个盘子，从j移到k，有两种方法，一种是传统的，另一种比较NB
例如从1到3 n个：1->2(n-1),1->3最大盘，2->3（n-1）
或者
1->3(n-1),1->2最大盘，3->1(n-1),2->3最大盘，1->3(n-1)
#include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) {f|=(ch==‘-‘); ch=getchar();} while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) {putchar(‘-‘); x=-x;} if(x<10) {putchar(x+‘0‘); return;} write(x/10); putchar((x%10)+‘0‘); } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) write(x),putchar(‘\n‘) int n; ll tim[5][5],dp[55][5][5]; int main() { // freopen("data.in","r",stdin); int i,j,k; memset(dp,63,sizeof dp); for(i=1;i<=3;i++) { for(j=1;j<=3;j++) { R(tim[i][j]); dp[0][i][j]=0; } } R(n); for(i=1;i<=n;i++) { for(j=1;j<=3;j++) for(k=1;k<=3;k++) if(j!=k) { int oo=6-j-k; dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][oo]+tim[j][k]+dp[i-1][oo][k]); dp[i][j][k]=min(dp[i][j][k],dp[i][j][oo]+dp[i-1][oo][j]+tim[oo][k]+dp[i-1][j][k]); dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+tim[j][oo]+dp[i-1][k][j]+tim[oo][k]+dp[i-1][j][k]); } } Wl(dp[n][1][3]); return 0; }
原文：https://www.cnblogs.com/gaojunonly1/p/11253209.html
