矩形嵌套問題：DAG 上的最長路徑（DP + 深搜）

建模與排序

• 將每個矩形統一為 (min(a,b), max(a,b))，即短邊在前
• 按短邊升序、長邊升序排序，保證嵌套關係只從前指向後，構成 DAG

狀態定義與轉移

• dp[i]：以第 i 個矩形為結尾的最長鏈長度
• dp[i] = max(dp[j]) + 1，對所有 j < i 且 rect[j] 可嵌套進 rect[i]
• 遞歸 + 記憶化搜尋（DFS）避免重複計算

圖的儲存優化

稠密圖 (n=1000 邊數近 5×10⁵) 用 vector 會因動態分配導致 TLE。改用靜態陣列鄰接表：

struct Edge { int to, next; } e[MAXE];
int head[MAXN], ecnt;
void addEdge(int u, int v) {
    e[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

或直接用鄰接矩陣 bool g[MAXN][MAXN]（1000² = 1e6，約 1 MB），建圖與查詢均為 O(1)，實測 12 ms 通過。

代碼骨架

int dfs(int u) {
    if (dp[u]) return dp[u];
    int ans = 1;
    for (int i = head[u]; ~i; i = e[i].next)
        ans = max(ans, dfs(e[i].to) + 1);
    return dp[u] = ans;
}

int main() {
    // ... 讀入、標準化、排序 ...
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (rect[i].x < rect[j].x && rect[i].y < rect[j].y)
                addEdge(i, j);
    int res = 0;
    for (int i = 0; i < n; ++i) res = max(res, dfs(i));
    printf("%d\n", res);
}

心得

• 稠密圖優先考慮鄰接矩陣或靜態鏈表，避免 vector 擴容開銷
• 排序後只需檢查 j > i，天然無環，DFS 無需訪問標記
• 狀態轉移方程直觀，記憶化搜尋代碼簡潔