HDU 4362 Dragon Ball：線段樹優化 DP 解決多階段決策問題

問題描述

有 n 層，每層 m 個位置，每個位置有坐標 pos 和代價 cos。從第 0 層起始位置 st 出發，每層必須選一個位置，移動代價為曼哈頓距離 |pos_i - pos_{i-1}|，總代價 = 移動代價和 + 所選位置代價和。求最小總代價。n ≤ 1000, m ≤ 50。

DP 定義與轉移

dp[i][j]：到達第 i 層第 j 個位置的最小代價。
轉移：dp[i][j] = cos[i][j] + min_k ( dp[i-1][k] + |pos[i][j] - pos[i-1][k]| )。

線段樹優化絕對值最小值查詢

固定第 i-1 層，對其位置按 pos 排序。對於第 i 層某位置 p，需求：

min_{k} ( dp[i-1][k] + |p - pos[k]| )
= min( min_{pos[k] ≤ p} (dp[i-1][k] - pos[k]) + p,
       min_{pos[k] ≥ p} (dp[i-1][k] + pos[k]) - p )

維護兩個線段樹（或一棵樹存兩個值），支持區間加法與全局最小值查詢。隨 p 遞增掃描，動態更新分界點，實現 O(m log m) 每層轉移。

核心代碼結構（關鍵片段）

struct Node { ll addv, mn; } seg[MAXN<<2];
vector a[MAXM]; // 每層按 pos 排序
ll dp[MAXM][MAXN];

void build(int layer, int p, int l, int r, int rt) {
    if (l == r) { seg[rt].mn = dp[layer][l] + abs(p - a[layer][l].pos); return; }
    int mid = (l+r)>>1;
    build(layer, p, l, mid, rt<<1);
    build(layer, p, mid+1, r, rt<<1|1);
    pushup(rt);
}

void update(int L, int R, ll v, int l, int r, int rt) { // 區間加法
    if (L <= l && r <= R) { seg[rt].mn += v; seg[rt].addv += v; return; }
    pushdown(rt);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, v, l, mid, rt<<1);
    if (R > mid) update(L, R, v, mid+1, r, rt<<1|1);
    pushup(rt);
}

// 主循環：對每層 i，以 a[i][0].pos 為基準建樹，
// 然後按 pos 遞增處理 a[i][j]，動態調整分界點並查詢全局最小值

複雜度分析

• 排序：O(n * m log m)
• 每層建樹：O(m)
• 每層掃描 m 個位置，每個位置 O(log m) 更新/查詢
• 總計：O(n * m log m) ≈ 1000 * 50 * 6 = 3e5 操作，極快。

關鍵技巧總結

1. 絕對值拆分：|x-y| = max(x-y, y-x) 轉化為兩個單調函數的最小值。
2. 線段樹維護兩個單調隊列：隨查詢點移動，區間加法模擬斜率變化。
3. 離線預處理：每層排序一次，DP 狀態按順序存取，避免動態插入。

總結

HDU 4362 是「DP + 線段樹優化絕對值轉移」的教科書級題目。核心在於將 min_k (dp[k] + |p - x_k|) 拆解為兩個前綴/後綴最小值，利用線段樹的區間加法與全局最小值查詢，將單層轉移從 O(m^2) 降為 O(m log m)。掌握此模式，可解決大量帶絕對值/凸函數轉移的 DP 問題。