HDU 1584 蜘蛛牌：區間 DP 最小移動步數

問題描述

10 張牌排成一行，每張有編號。操作：將一張牌移到另一張牌上（疊加），代價 = 兩牌位置距離。求將所有牌疊成一疊的最小總代價。

區間 DP 狀態定義

f[i][j]：將區間 [i,j] 內的牌疊成一疊（最終位置在 k）的最小代價。但最終位置不固定，需枚舉。

優化狀態：f[i][j] 表示將 i..j 疊成一疊的最小代價，**不固定最終位置**，轉移時枚舉「下一張牌」的最終位置。

轉移方程

// d[x][y] = 牌 x 到 牌 y 的初始距離
for (len=1; len<10; len++)
  for (i=1; i+len<=10; i++) {
    int j = i+len;
    f[i][j] = INF;
    for (k=i+1; k<=j; k++) // 枚舉 i+1 這張牌最終所在位置 k
      f[i][j] = min(f[i][j], f[i+1][k] + f[k][j] + d[i][k]);
  }

關鍵洞察

最優策略遞歸構造：先將 i+1..k 疊在 k，再將 k..j 疊在 k，最後將 i 移到 k（代價 d[i][k]）。枚舉 k 覆蓋所有可能。初始 f[i][i]=0。

代碼實現

int a[15], d[15][15], f[15][15];
void dp() {
    for (int i=0;i<10;i++)
        for (int j=1;j<=10;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]);
        }
}

總結

HDU 1584 是經典「區間 DP + 枚舉分割點」問題。關鍵在於狀態定義不固定最終位置，轉移時枚舉中間牌的歸宿位置。n=10 極小，O(n^3) 輕鬆過。此模板廣泛適用於「合併/疊加」類區間優化問題。