模拟赛中出到了类似题，特意在网上搜索学习，并有所感想

本文由此获得启发，特此感谢

PART1. LIS

从P1439 【模板】最长公共子序列开始

50pt的$O(n^2)$算法很容易想，即设f[i]表示到i结束的最长LIS的长度

再来看100pt的限制，要求的是$O(n log n)$的算法

我们发现n方算法的复杂度瓶颈在于那个max，但同时我们有注意到$j<i$这个条件，这意味着max是可以前缀维护的

前缀最大可以用树状数组维护（当然本题打分块，线段树也可以），记录比排名第i的元素小的数前面有几个出现了

代码很好实现，要注意的是，当数字很大时要先离散化一下再搞

当然，LIS还可以用二分做，但适用范围较小，这里就不再赘述了

PART2. LCS

（下文将把LCS中的两个串称为A和B）

LCS与LIS很类似，通常有两种思路，下面将分别从不同的例题进行讲解

WAY1. 将B串元素按各自在A串中的位置进行映射，转化成一个LIS问题
例题：UVA10635 Prince and Princess

题意：给你两个串，求最长公共子序列

我们将LIS问题与LCS问题作比较，发现LIS其实是LCS的一个特殊版本，即A串中的元素递增且都在B中出现，求AB的LCS

既然是特殊版本，那我们把不特殊的搞特殊了不就好了吗？

既然LIS中数的顺序是1、2、3。。。，那我们就把LCS中数的顺序理解为$A_1、A_2、A_3。。。$

这样十分自然的只需要遍历一遍A，记录各元素在新顺序里的位置，再将B串映射过去跑一边LIS就好了

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=5e5+5;
int n,a[N],b[N],p,q,pos[N],f[N];
struct BIT{
    #define lowbit(x) (x&(-x))
    int a[N];
    void clear(){
        memset(a,0,sizeof a);
    }
    void up(int x,int v){
        while(x<=n){
            a[x]=max(a[x],v);
            x+=lowbit(x);
        }
    }
    int que(int x){
        int res=0;
        while(x){
            res=max(res,a[x]);
            x-=lowbit(x);
        }
        return res;
    }
}ma;
void doit(){
    int ans=0;
    read(n),read(p),read(q);
    p++;q++;
    n=p;
    ma.clear();
    memset(pos,0,sizeof pos);
    for(int i=1;i<=p;i++) read(a[i]),pos[a[i]]=i; //记录各元素在A中位置
    for(int i=1;i<=q;i++) read(b[i]),b[i]=pos[b[i]]; //映射
    for(int i=1;i<=q;i++) if(b[i]){
        f[i]=ma.que(b[i]-1)+1; //累计各元素前有几个比它小的出现过了
        ans=max(ans,f[i]);
        ma.up(b[i],f[i]);
    }
    write(ans);puts("");
}
signed main(){
    int t;
    read(t);
    for(int i=1;i<=t;i++) printf("Case %d: ",i),doit();
}
WAY2. 从n方dp出发，进行优化
例题：P4303 [AHOI2006]基因匹配

题意：给你两个串，保证串中的每个元素都会出现5次，求最长公共子序列

如果用way1，我们发现重复的数字会使映射变得很麻烦

这时我们重新考虑$O(n^2)$的dp，设f[i][j]表示允许使用A的前i个元素，B的前j个元素（其中第i个，第j个元素不要求必须使用），所能得到的最长公共子序列

空间会炸，但此时无法使用滚存，我们不得不修改dp状态，考虑从f[i-1][]求出f[i][]，即设f[i][j]表示允许使用第一个序列的前i个元素，第二个序列的前j个元素（其中第一个序列第i个元素不必须使用，第二个序列第j个元素必须使用）

这样第一维就可以被滚掉了，假如$A_i=B_k$，那么修改f[k]即可。

空间问题解决了，但时间还会炸，与LIS相同的套路，复杂度瓶颈还是在于max，同样用树状数组维护前缀最大即可

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=1e5+5;
int a[N],b[N],n,f[N],ans;
vector<int> p[N/5];
struct BIT{
    #define lowbit(x) (x&(-x))
    int a[N];
    void up(int x,int v){
        while(x<=n){
            a[x]=max(a[x],v);
            x+=lowbit(x);
        }
    }
    int que(int x){
        int res=0;
        while(x){
            res=max(res,a[x]);
            x-=lowbit(x);
        }
        return res;
    }
}ma;
signed main(){
    read(n);
    n*=5;
    for(int i=1,x;i<=n;i++) p[read(x)].push_back(i); //记录每个元素的位置k
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<=n;i++)
        for(int j=4;j>=0;j--){ //各出现5次
            int pos=p[b[i]][j];
            f[pos]=ma.que(pos-1)+1; //对该位置前面的进行修改
            ma.up(pos,f[pos]);
        }
    for(int i=1;i<=n;i++) ans=max(ans,f[i]); //遍历dp数组取极值
    write(ans);
}

PART3. 一道例题

模拟赛中出现了一道LCS模板题，只是我当时没看出来。。。

P3657 [USACO17FEB]Why Did the Cow Cross the Road II P

大致思路是把问题看成将普通LCS的相等的条件改为差的绝对值<=4

题解我另写了，代码、思路的见这里

赏

OIer