简介

本题解带三种动态规划LCS模型的解法，普通解法，空间优化LCS->LIS，树状数组LIS
讲解待补充...可以留言催更...

空间O(n^2) 时间O(n^2)代码段

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

空间O(n) 时间O(n^2)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6+10;

int f[N],g[N];
int n;
pair<int,int> a[N];
int b[N],_b[N];


int b_find(int x){
    int l = 1, r = n;
    while(l < r){
        int mid = l+r+1>>1;
        if(a[mid].first <= x)l=mid;
        else r = mid-1;
    }
    return l;
}


int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1,a+1+n);

    for(int i = 1; i <= n; i++){
        cin >> b[i];
        int t = b_find(b[i]);
        if(a[t].first == b[i]){
            _b[i] = a[t].second;
        }else{
            _b[i] = 0;
        }
    }
    _b[0] = 0x3f3f3f3f;
    f[0] = -1;
    for(int i = 1; i <= n; i++){
        if(_b[i] != 0)f[i] = 1;
        for(int j = 1; j < i; j++){
            if(_b[i] > _b[j])f[i] = max(f[j]+1,f[i]);
        }
    }

    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        res = max(res,f[i]);
    }
    cout << res;
    return 0;
}

空间O(n) 时间O(nlogn)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6+10;

int n;
int f[N];
pair<int,int> a[N];
int b[N],_b[N];

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)

int b_find(int x){
    int l = 1, r = n;
    while(l < r){
        int mid = l+r+1>>1;
        if(a[mid].first <= x)l=mid;
        else r = mid-1;
    }
    return l;
}

int lowbit(int x){
    return x&-x;
}

void update(int pos, int x){
    while(pos <= n){
        f[pos] = max(f[pos],x),pos+=lowbit(pos);
    }
}

int query(int pos){
    int res = -0x3f3f3f3f;
    while(pos){
        res = max(res,f[pos]),pos-=lowbit(pos);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1,a+1+n);

    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        int t = b_find(b[i]);
        if(a[t].first == b[i]){
            _b[i] = a[t].second;
            update(_b[i],1);
            int val = query(_b[i]-1);
            update(_b[i],val+1);
            res = max(res,val+1);
        }
    }

    cout << res << endl;
    return 0;
}