跳转至

最长上升子序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// B3637 最长上升子序列 !important
// 线性动态规划 O(nlogn)
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e4 + 9;
int d[MAXn], dp[MAXn], h[MAXn];

int main() {
    for(int i = 1; i <= MAXn - 3; i ++)
        h[i] = INT_MAX;    // 下降：h[i] = INT_MIN;
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]);
    int m = 0;
    for(int i = 1; i <= n; i ++) {
        dp[i] = 1;    // 一定包含自己的以自己结尾的最长XX子序列长度
        // 波式二分，在 h 数组中二分找到小于/大于[等于]要二分的 d[i] 的值
        int p = 0;
        for(int j = 20; j >= 0; j --) {
            int pp = p | (1 << j);
            if(pp <= m && h[pp] < d[i]) p = pp;    // 下降：h[pp] > d[i]
        }
        dp[i] = p + 1;    // 二分出的 dp[i] 的值
        m = max(m, dp[i]);    // 最长的序列值，也是 h 数组的最后一位
        h[dp[i]] = min(h[dp[i]], d[i]);    // 下降：max(h[dp[i]], d[i])
        // h[i]: 长度为 i 的序列的最后一位的最小/大值，升 min 降 max
    }
    // int ans = 0;
    // for(int i = 1; i <= n; i ++)
    //     ans = max(ans, dp[i]);
    printf("%d", m);
    return 0;
}