BZOJ 1107 駕駛考試：LIS 與樹狀數組優化 DP

問題描述

給定一條道路，有起點、終點和若干中間點。某些點之間有單向道路（上坡/下坡）。求最長可行駛路徑長度，並扣除起始即可到達所有終點的點數。（具體題意較複雜，核心為求最長上升子序列變體）。

解題思路

將問題轉化為：對於每個位置 i，計算以 i 結尾的最長合法序列長度。利用樹狀數組（BIT）維护前綴/後綴最大值，實現 O(n log n) DP。具體做法：

1. 將上坡和下坡邊分開處理，按位置排序。
2. 正向遍歷計算 l[i]：從左到右，用 BIT 查詢小於當前值的最大 DP 值並更新。
3. 反向遍歷計算 r[i]：從右到左，類似處理。
4. 雙指針滑動窗口找最大區間長度使得 l[i] + r[j] <= k。
5. 最後扣除 l[i]==0 && r[i]==0 的點。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 100100;
struct Item { int pos, val; };
Item up[MAXN], down[MAXN];
int bit[MAXN], l[MAXN], r[MAXN];
int n, m, p, k;

void bitUpdate(int idx, int val) {
    for (; idx > 0; idx -= idx & -idx) bit[idx] = max(bit[idx], val);
}
int bitQuery(int idx) {
    int res = 0;
    for (; idx <= m; idx += idx & -idx) res = max(res, bit[idx]);
    return res;
}

int main() {
    cin >> n >> m >> p >> k;
    ++m;
    int uc = 0, dc = 0;
    for (int i = 0; i < p; ++i) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        ++y;
        if (z) up[++uc] = {x+1, y};
        else down[++dc] = {x, y};
    }
    sort(up+1, up+uc+1, [](Item a, Item b){ return a.pos != b.pos ? a.pos < b.pos : a.val < b.val; });
    sort(down+1, down+dc+1, [](Item a, Item b){ return a.pos != b.pos ? a.pos > b.pos : a.val < b.val; });
    // 正向 DP
    memset(bit, 0, sizeof(bit));
    for (int i = 1, j = 1; i <= n; ++i) {
        l[i] = l[i-1] + 1;
        for (; j <= uc && up[j].pos == i; ++j) {
            int dp = bitQuery(up[j].val) + 1;
            l[i] = min(l[i], (i-1) - dp);
            bitUpdate(up[j].val, dp);
        }
    }
    // 反向 DP
    memset(bit, 0, sizeof(bit));
    for (int i = n, j = 1; i >= 1; --i) {
        r[i] = r[i+1] + 1;
        for (; j <= dc && down[j].pos == i; ++j) {
            int dp = bitQuery(down[j].val) + 1;
            r[i] = min(r[i], (n-i) - dp);
            bitUpdate(down[j].val, dp);
        }
    }
    // 滑動窗口
    int ans = 0;
    for (int i = 1, j = 1; i <= n; ++i) {
        while (i - j + 1 > 0 && l[i] + r[j] > k) ++j;
        ans = max(ans, i - j + 1);
    }
    for (int i = 1; i <= n; ++i) if (l[i] == 0 && r[i] == 0) --ans;
    cout << ans << endl;
    return 0;
}

複雜度分析

• 時間複雜度：O((n + p) log m)。
• 空間複雜度：O(n + m)。

總結

本題結合了 LIS、樹狀數組優化 DP 和滑動窗口，展示了如何將複雜約束轉化為可高效計算的子問題。代碼結構清晰，值得學習。