Codeforce 392B Tower of Hanoi 区间dp

给定一个3*3的矩阵 [i,j] 表示把一个盘子从第i根柱子移到第j跟柱子的花费

下面一行n表示一共有n个盘子在1号柱子

问：全部都移动到3号柱子的最小花费

思路：

显然是一个区间dp

dp[num][i][j] 表示把num个盘子从 i->j 需要的最小花费

注意dfs是表示在上方的盘子移动的最小花费

在底部的那个盘子移动是 矩阵的花费

inf一定要足够大 1e18

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define inf 1000000000000000000 #define ll __int64 ll n; ll map[3][3]; ll dp[42][3][3]; ll dfs(ll num, ll s, ll t){ if(dp[num][s][t]