acwing-895. 最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000，
?109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

方法一：

状态表示：f(i) = max(以第i个元素结尾的子序列长度的集合)

#include 

using namespace std;

const int N = 510;
int n, a[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            scanf("%d", &a[i][j]);
        }
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= i; ++j) {
            a[i][j] += max(a[i+1][j], a[i+1][j+1]);
        }
    }

    printf("%d", a[1][1]);
}

方法二：

DP + 二分 by VictorWu，思路清奇真的是，不容易

• 状态表示：f[i]表示长度为i的最长上升子序列，末尾最小的数字。(长度为i的最长上升子序列所有结尾中，结尾最小min的) 即长度为i的子序列末尾最小元素是什么。

• 状态计算：对于每一个w[i], 如果大于f[cnt-1]（下标从0开始，cnt长度的最长上升子序列，末尾最小的数字），那就cnt+1，使得最长上升序列长度+1，当前末尾最小元素为w[i]。 若w[i]小于等于f[cnt-1],说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于 (这里不能是大于) w[i]，更新以那时候末尾的最小元素。

• f[i]一定以一个单调递增的数组，所以可以用二分法来找第一个大于或等于w[i]的数字。

#include 

using namespace std;

const int N = 1010;
int n, cnt;
int w[N], f[N];

int main() {
    cin >> n;
    for (int i = 0 ; i < n; i++) cin >> w[i];

    f[cnt++] = w[0];
    for (int i = 1; i < n; i++) {
        if (w[i] > f[cnt-1]) f[cnt++] = w[i];
        else {
            int l = 0, r = cnt - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (f[mid] >= w[i]) r = mid;
                else l = mid + 1;
            }
            f[r] = w[i];
        }
    }
    cout << cnt << endl;
    return 0;
}