最长公共子序列(局限性)(LCS)问题

//原理:dp
//时间复杂度:o(n^2),过不了本题
#include <bits/stdc++.h>
using namespace std;
int f[1001][1001];//dp数组,f[i][j]为处理了a的前i位,b的前j位得到的最长公共子序列
int a[1001];
int b[1001];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//加快输入输出
    int n;
    cin>>n;
    for (int i = 1;i<=n;i++) cin>>a[i];
    for (int i = 1;i<=n;i++) cin>>b[i];
    for (int i = 1;i<=n;i++)//dp,处理f[i][j]
    {
        for (int j = 1;j<=n;j++)
        {
            if(a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;//如果当前a[i] == b[j],则可以长度加1
            else f[i][j] = max(f[i-1][j],f[i][j-1]);//否则转移最大值(观察下标,之前的已经计算过了)
        }
    }
    cout<<f[n][n]<<"\n";//输出答案
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
map<int,int> b;//用哈希表不一定有红黑树快,对于可能卡哈希的,而红黑树一定过的,优先用红黑树(acmer的严谨,我这里不管)
int a[100001];//a数组
int cvt[100001];//转换得到的cvt数组
int low[100001];//长度为i的LIS的最后一个数的最小值
int m = 0;//LIS最大长度,初始化为0
int Find(int x)//二分查找
{
    int ans = 0;//初始化答案
    int l = 0;
    int r = m;
    while(l<=r)//二分
    {
        int mid = (l+r)>>1;
        if(low[mid] >= x)//一定要等于,否则就不满足LIS性质了(即单调上升,可能会导致单调不减)
        {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//加快输入输出
    memset(low,-127,sizeof(low));//low数组初始化为负无穷,防止新的数比low[1]还小的情况的Hack!(自己感悟)
    int n,x;
    cin>>n;//输入数量
    for (int i = 1;i<=n;i++) cin>>a[i];//输入a数组
    for (int i = 1;i<=n;i++)//处理b数组
    {
        cin>>x;
        b[x] = i;//记下位置
    }
    for (int i = 1;i<=n;i++)//生成cvt数组
    {
        cvt[i] = b[a[i]];
    }
    for (int i = 1;i<=n;i++)//LIS模板
    {
        if(cvt[i]>low[m]) low[++m] = cvt[i];//直接接上
        else
        {
            int p = Find(cvt[i]);
            low[p] = cvt[i];//更新位置最小值
        }
    }
    cout<<m<<"\n";//输出答案,即LIS长度
    return 0;
}