POJ 1609 Tiling Up Blocks：記憶化搜尋入門

題目大意

給定 n 個二元組 (a, b)，需從中找出最長序列，使得對序列中任意 i < j，滿足 a_i ≤ a_j 且 b_i ≤ b_j。輸入包含多組測試資料，n=0 結束。

解題思路：記憶化搜尋

定義 dp[a][b] 為以 (a, b) 結尾的最長合法序列長度。對於每個存在的點 (x, y)，其值等於所有滿足 i≤x、j≤y 且 (i,j)≠(x,y) 的點中最大 dp 值，加上該點的出現次數 num[x][y]。由於座標範圍較小（≤128），可直接用二維陣列儲存並遞歸計算。

遞歸關係

dp[x][y] = max{ dp[i][j] } + num[x][y]   (1≤i≤x, 1≤j≤y, (i,j)≠(x,y))

利用記憶化避免重複計算，時間複雜度約 O(maxA·maxB·maxA·maxB)，實際上因稀疏性遠小於此。

完整代碼 (C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_P = 128;
int n;
int num[MAX_P][MAX_P];
int dp[MAX_P][MAX_P];

int search(int x, int y) {
    if (dp[x][y]) return dp[x][y];
    int maxv = 0;
    for (int i = 1; i <= x; ++i)
        for (int j = 1; j <= y; ++j)
            if (!(i == x && j == y) && num[i][j])
                maxv = max(maxv, search(i, j));
    return dp[x][y] = maxv + num[x][y];
}

int main() {
    while (scanf("%d", &n) == 1) {
        if (n == 0) { printf("*\n"); break; }
        memset(num, 0, sizeof(num));
        memset(dp, 0, sizeof(dp));
        int maxA = 0, maxB = 0;
        for (int i = 0; i < n; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            ++num[a][b];
            maxA = max(maxA, a);
            maxB = max(maxB, b);
        }
        int ans = 0;
        for (int i = 1; i <= maxA; ++i)
            for (int j = 1; j <= maxB; ++j)
                if (num[i][j]) ans = max(ans, search(i, j));
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點總結

• 狀態定義直觀：以某點結尾的最長序列
• 記憶化搜尋簡化拓撲序處理
• 座標範圍小，二維陣列足夠
• 同一座標可能出現多次，用 num 計數