UVA 10051 Tower of Cubes：立方體疊塔的 DP + 路徑重構

題目大意

給定 n ≤ 500 個立方體，每面有顏色。疊塔規則：上方立方體的底面顏色 = 下方立方體的頂面顏色。每個立方體最多用一次，求最高塔高度並輸出構造方案（立方體編號+頂面名）。

關鍵建模

1. 將立方體按權重從大到小排序（或按輸入順序反序），保證只從「較大/較早」向「較小/較晚」轉移，避免環。
2. 狀態：dp[i][f] 表示以第 i 個立方體的第 f 面作為頂面的最高塔高度。
   對應底面為 opp[f] = 5-f（對應面索引和為 5）。
3. 轉移：dp[i][f] = max( dp[j][g] + 1 )，其中 j < i 且 color[i][opp[f]] == color[j][g]（當前底面匹配前一頂面）。
4. 初始：dp[i][f] = 1（單獨成塔）。

路徑重構

用 pre[i][f] = {j, g} 記錄最優轉移來源。最終找到全局最大 dp[i][f]，回溯輸出。

C++ 代碼

#include 
using namespace std;
const int MAXN = 505;
int color[MAXN][6];          // 0:front,1:left,2:top,3:bottom,4:right,5:back
int dp[MAXN][6];
pair pre[MAXN][6];
const string faceName[6] = {"front","left","top","bottom","right","back"};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, tc = 0;
    while (cin >> n, n) {
        if (tc++) cout << '\n';
        // 反序讀入，使較大索引在下方
        for (int i = n; i >= 1; --i) {
            for (int f = 0; f <= 2; ++f) {
                cin >> color[i][f];
                color[i][5-f] = color[i][f]; // 對應面
            }
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i)
            for (int f = 0; f < 6; ++f)
                dp[i][f] = 1, pre[i][f] = {-1,-1};
        for (int i = 1; i <= n; ++i) {
            for (int f = 0; f < 6; ++f) {
                int bottom = color[i][5-f]; // 當前作為頂面f時的底面顏色
                for (int j = 1; j < i; ++j) {
                    for (int g = 0; g < 6; ++g) {
                        if (color[j][g] == bottom && dp[i][f] < dp[j][g] + 1) {
                            dp[i][f] = dp[j][g] + 1;
                            pre[i][f] = {j, g};
                        }
                    }
                }
            }
        }
        int best = 0, bi = -1, bf = -1;
        for (int i = 1; i <= n; ++i)
            for (int f = 0; f < 6; ++f)
                if (dp[i][f] > best) { best = dp[i][f]; bi = i; bf = f; }
        cout << "Case #" << tc << '\n' << best << '\n';
        while (bi != -1) {
            cout << (n - bi + 1) << ' ' << faceName[bf] << '\n'; // 原始輸入順序編號
            auto [pi, pf] = pre[bi][bf];
            bi = pi; bf = pf;
        }
    }
    return 0;
}

複雜度

• 時間：O(n² × 36) ≈ 9×10⁶，n=500 時極快。
• 空間：O(n × 6)。

關鍵技巧總結

1. 反序輸入 + 正序 DP：天然形成 DAG，無需額外拓撲排序。
2. 對應面索引和為 5：輸入時直接填入 color[i][5-f]，轉移時 O(1) 取底面。
3. 記錄前驅重構路徑：pair pre[][] 簡潔高效。

總結

UVA 10051 是「帶狀態的最長路徑 + 輸出方案」的經典題。核心模式：排序構造 DAG → 狀態 DP → 記錄前驅回溯。同類模板適用於 UVA 10131、POJ 1015 等疊箱子/疊塔問題。