LIS,LCS,LCIS的前世今生

Lazystone · 2019-11-03 19:59:15 · 个人记录

• 没有前世（已经忘了），不一定有今生（还没学会）

  LIS——最长上升子序列

• prefer树状数组写法
• 板子：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
//#define getchar nc
inline int read(){
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
const int N=5050;
int n,ans;
struct cgx{
    int id,num;
    bool operator < (const cgx &a)const{
        return num<a.num||(a.num==num&&id>a.id);
        //按照序号从大到小可以保证所求为上升子序列
        //(针对标号)因为相同权值的数，前面的状态不能转移给后面
        //(针对标号)从大到小枚举就不会出现这种情况
    }
}a[N];
int bit[N];
void update(int x,int w){
    for(;x<=n;x+=x&(-x))bit[x]=max(bit[x],w);
}
int query(int x){
    int ret=-1e9;
    for(;x;x-=x&(-x))ret=max(ret,bit[x]);
    return ret;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i].id=i,a[i].num=read();
    sort(a+1,a+n+1);
    for(int len,i=1;i<=n;i++){
        len=query(a[i].id);
        update(a[i].id,++len);
        ans=max(ans,len);
    }
    printf("%d\n",ans);
    return 0;
}

LCS——最长公共子序列

• 比较朴素而显然的 O(n^2) 算法

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
//#define getchar nc
inline int read(){
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
const int N=1e5+10;
int n;
int a[N],b[N];
int f[N][N]
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i-1]==b[i-1])f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
    printf("%d\n",f[n][n]);
    return 0;
}

• 但是遇到这道题就跪了，发现 n 的范围 10^6 ，O(n^2) 肯定凉
• 但是它又有特殊的地方：两个数列都是 1-n 的排列，说明两数列的元素相同只是位置不同，于是可以转换成求最长上升子序列
• 转换？两个数列 a,b ，我们可以把 a 中的数值映射成它的下标，再把 b 中的元素映射到 a 的下标顺序，这样就已经保证 a 有序了，那么最长公共子序列也要保持单增，又因为 b 中的任意单增的序列都是现在映射完的单增的 a 的子序列，所以问题转化为最长上升子序列（没有重复元素）

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
//#define getchar nc
inline int read(){
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
const int N=1e5+10;
int n,ans;
int a[N],ref[N];
struct cgx{
    int id,num;
    bool operator < (const cgx &a)const{
        return num<a.num||(num==a.num&&id>a.id);
    }
}b[N];
int bit[N];
void update(int x,int w){
    for(;x<=n;x+=x&(-x))bit[x]=max(bit[x],w);
}
int query(int x){
    int ret=-1e9;
    for(;x;x-=x&(-x))ret=max(bit[x],ret);
    return ret;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read(),ref[a[i]]=i;
    for(int i=1;i<=n;i++){
        b[i].num=read();
        b[i].num=ref[b[i].num];
        b[i].id=i;
    }
    sort(b+1,b+n+1);
    for(int len,i=1;i<=n;i++){
        len=query(b[i].id);
        update(b[i].id,++len);
        ans=max(ans,len);
    }
    printf("%d\n",ans);
    return 0;
}