题目

#include <iostream>

int n, cnt;

using namespace std;
int a[1200], dp[1200];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    dp[cnt++] = a[0];
    for (int i = 1; i < n; i++) {
        int la = 0, r = cnt, v = a[i];
        if (v > dp[cnt-1]) dp[cnt++] = v;
        else {
            while (la < r - 1) {
                int m = la + r >> 1;
                if (dp[m] >= v) r =m;
                else la = m;
            }
            if (dp[la] >= v) r = la;
            dp[r] = v; 
        }
    }
    //for (int i = 0; i < n+1; i++) cout << dp[i] << ' ';
    cout << cnt << endl;
    return 0;
}

平时写的二分是找小于或者等于v的第一个数，取dp[l] = v;
这次找大于v的第一个数，取dp[r] = v; 加一句if (dp[la] >= v) r = la; 就可以

这里赋值dp[r] = v;

因为整数除法的特性, 没有这一句if的话，
la的取值范围是 la 到 N-1;
r的取值范围是 la + 1 到 N-1

加上这一句使r的取值范围变成了 la 到 N-1

lowerbound和upperbound的用法

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

lower_bound( begin,end,num,greater[HTML_REMOVED]()):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater[HTML_REMOVED]() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include <iostream>

int n, cnt;

using namespace std;
int a[1200], dp[1200];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    dp[cnt++] = a[0];
    for (int i = 1; i < n; i++) {
        int la = 0, r = cnt, v = a[i];
        if (v > dp[cnt-1]) dp[cnt++] = v;
        else {
            int pos = lower_bound(dp, dp + cnt, v) - dp;
            dp[pos] = v;
        }
    }
    //for (int i = 0; i < n+1; i++) cout << dp[i] << ' ';
    cout << cnt << endl;
    return 0;
}

这道题要用lower bound