您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

LightOJ 1085 All Possible Increasing Subsequences：DP + 離散化 + 樹狀數組

編輯：C++ 入門

題目大意

給定長度為 n 的序列，求所有嚴格遞增子序列的個數，結果模 1000000007。多組測試數據。

核心思路：動態規劃 + 樹狀數組優化

設 dp[i] 為以第 i 個元素結尾的遞增子序列數。則 dp[i] = 1 + sum(dp[j])，其中 j < i 且 a[j] < a[i]。直接雙層循環為 O(n^2) 會超時。利用樹狀數組維护前綴和，可將轉移優化至 O(log n)，總複雜度 O(n log n)。

關鍵技巧：從右下往左上的離散化

常規離散化是按值從小到大排序，但這裡採用一種巧妙的「從右下往左上看」的排序規則：

先按值 a[x] 升序。
值相同時，按原下標 x 降序。

這樣處理後，遍歷排序後的下標順序更新樹狀數組，恰好能保證同值元素不會互相影響（因為嚴格遞增要求 a[j] < a[i]），且無需額外處理相同值的分組，代碼極其簡潔高效。

兩種實現對比

方法一：右下往左上離散化（推薦，0.364s）

/* 0.364s, 2860KB */
#include <bits/stdc++.h>
using namespace std;
const int MX = 100005;
const int MOD = 1000000007;
int tree[MX], a[MX], dis[MX], n;

bool cmp(int x, int y) {
    if (a[x] != a[y]) return a[x] < a[y];
    return x > y; // 值相同時，下標大的在前
}

void add(int pos, int val) {
    for (; pos <= n; pos += pos & -pos)
        tree[pos] = (tree[pos] + val) % MOD;
}

int sum(int pos) {
    int res = 0;
    for (; pos; pos -= pos & -pos)
        res = (res + tree[pos]) % MOD;
    return res;
}

int main() {
    int T, cas;
    scanf("%d", &T);
    for (cas = 1; cas <= T; ++cas) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), dis[i] = i;
        sort(dis + 1, dis + n + 1, cmp);
        memset(tree, 0, sizeof(tree));
        for (int i = 1; i <= n; ++i)
            add(dis[i], sum(dis[i]) + 1); // +1 代表自身構成長度為1的子序列
        printf("Case %d: %d\n", cas, sum(n));
    }
    return 0;
}

方法二：常規 map 離散化（較慢，1.236s）

/* 1.236s, 7088KB */
#include <bits/stdc++.h>
using namespace std;
const int MX = 100005;
const int MOD = 1000000007;
int tree[MX], a[MX], n;
map<int, int> mp;

void add(int pos, int val) {
    for (; pos <= n; pos += pos & -pos)
        tree[pos] = (tree[pos] + val) % MOD;
}
int sum(int pos) {
    int res = 0;
    for (; pos; pos -= pos & -pos)
        res = (res + tree[pos]) % MOD;
    return res;
}
int main() {
    int T, cas;
    scanf("%d", &T);
    for (cas = 1; cas <= T; ++cas) {
        scanf("%d", &n);
        mp.clear();
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]), mp[a[i]];
        int cnt = 0;
        for (auto &it : mp) it.second = ++cnt; // 離散化賦值
        memset(tree, 0, sizeof(tree));
        for (int i = 0; i < n; ++i) {
            int pos = mp[a[i]];
            add(pos, sum(pos - 1) + 1);
        }
        printf("Case %d: %d\n", cas, sum(cnt));
    }
    return 0;
}