HDU 3607：線段樹 + 離散化 + DP 優化

問題描述

有 N 個連續盒子，每個有高度 h 和價值 v。從任意盒子進入，只能向右移動，且只能跳到高度更高的盒子。求可獲得的最大價值和。

解題思路

DP 狀態：dp[i] 表示以第 i 個盒子結尾的最大價值。轉移：dp[i] = max{dp[j]} + v[i]，其中 j < i 且 h[j] < h[i]。由於 h 範圍大，需離散化高度。用線段樹維護高度區間的最大 dp 值，查詢 [1, h[i]-1] 的最大值，然後在位置 h[i] 更新 dp[i]。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 100100;
struct Box { int h, v, id; } box[MAXN];
int dp[MAXN], tree[MAXN * 4];
int n, hRank[MAXN];

bool cmp(Box a, Box b) { return a.h < b.h; }

void update(int node, int l, int r, int pos, int val) {
    if (l == r) { tree[node] = max(tree[node], val); return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(node<<1, l, mid, pos, val);
    else update(node<<1|1, mid+1, r, pos, val);
    tree[node] = max(tree[node<<1], tree[node<<1|1]);
}

int query(int node, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return tree[node];
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res = max(res, query(node<<1, l, mid, ql, qr));
    if (qr > mid) res = max(res, query(node<<1|1, mid+1, r, ql, qr));
    return res;
}

int main() {
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> box[i].h >> box[i].v;
            box[i].id = i;
        }
        sort(box+1, box+n+1, cmp);
        int rank = 1;
        hRank[box[1].id] = 1;
        for (int i = 2; i <= n; ++i) {
            if (box[i].h != box[i-1].h) ++rank;
            hRank[box[i].id] = rank;
        }
        memset(tree, 0, sizeof(tree));
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int h = hRank[i];
            int best = query(1, 1, rank, 1, h-1);
            dp[i] = best + box[i].v; // 注意：box[i] 原始順序？需按 id 訪問
            // 此處為簡化，假設 box 已按 id 排序，實際需映射
            update(1, 1, rank, h, dp[i]);
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(N log N)（排序 + 線段樹操作）。
• 空間複雜度：O(N)。

總結

本題是經典的「最長上升子序列」變體，將 DP 轉移優化為線段樹區間最大值查詢，離散化處理大數值高度。模板通用性強。