题目链接

分析：
f[i][j] 表示 把一串牌 牌 i 到 j 摞为一摞 时花费最少的步数。
d[i][j] 表示把牌 i 挪到牌 j 上时需要走的步数（最初给的状态）。
以一串牌 3~8 为例， 我们需要把牌 3 放到牌 4 上 ， 而在最优的移动方案下， 牌 4 的位置不确定， 所以我们枚举牌 4 所在的位置（因为一共10张牌， 枚举是可以的）， 这样得出状态转移方程： f[3][8] = min(f[3][8], f[4][k] + f[k][8] + d[3][k]); ( 4 <= k <= 8)。 f[i][j] = min (f[i][j], f[i+1][k] + f[k][j] + d[i][k]);

举个例子： 牌的初始顺序为 1， 4， 6， 8， 3， 2， 5， 7， 9， 10
求f[1][4] 时。 最有顺序应该是 ： 先把牌 2 移到 牌 3 上， 把牌 2~3 移到牌 4 上。 最后 把牌 1 移到 牌 2 上。 而此时牌 2 已经在 牌4 的位置上了。（f[1][4] = f[2][4] + f[4][4] + d[1][4] = 5）。

#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          using namespace std; int t, a[15], d[15][15], f[15][15]; void dp() { for(int i = 0; i < 10; i++)//所求的区间不断增大， 先求距离小的区间， 得出最优子问题解 { for(int j = 1; j <= 10; j++)//所求将一串牌 j 到 i+j 摞成一摞时最小步数。 { if(i + j > 10) continue; for(int k = j + 1; k <= i + j; k++)//枚举上一张牌所在的位置 f[j][i+j] = min(f[j][i+j], f[j+1][k] + f[k][i+j] + d[j][k]); } } } void Init() { for(int i = 1; i <= 10; i++) scanf("%d", &a[i]); memset(d, 0, sizeof(d)); for(int i = 1; i <= 10; i++)//将所有距离预处理下 { for(int j = 1; j <= 10; j++) { int x = a[i], y = a[j]; d[x][y] = abs(i - j); d[y][x] = d[x][y]; } } } int main() { cin >> t; while(t--) { for(int i = 1; i <= 10; i++) { for(int j = 1; j <= 10; j++) { f[i][j] = 10e8; if(i == j) f[i][j] = 0; } } Init(); dp(); printf("%d\n", f[1][10]); } return 0; }