LIS,LCS,LICS学习笔记

for(int i=1;i<=n;i++){
    f[i]=1;
    for(int j=1;jif(a[j]1,f[i]);
    }
}

O(nlogn):
1. 用一个数组(栈)来维护最可能成为LIS的序列 （和DP没有关系）
2. 用树状数组来优化第二种DP（有推广意义）。

1 3 5 6 4 7 8
[1,3,5,6] 4
[1,3,4(5),6] 5
[1,3,4(5),5(6),6]
向前查找位置（二分或STL）nlogn
upper_bound: “元素值>查找值”的第一个元素的位置
lower_bound: “元素值>=查找值”的第一个元素的位置

#include
#include
#include
using namespace std;

int a[40005];
int d[40005];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n==0) 
    {
        printf("0\n");
        return 0;
    }
    d[1]=a[1]; 
    int len=1;
    for (int i=2;i<=n;i++)
    {
        if (a[i]>d[len]) d[++len]=a[i];  
        else  {
            int j=lower_bound(d+1,d+len+1,a[i])-d;  //找到第一个>=它的d的下标 
            d[j]=a[i]; 
        }
    }
    printf("%d\n",len);  
    return 0;
}

树状数组： 1. 求前缀和， 2.单点加减

int ask(int pos){
    int ret=0;
    while(pos>0){
        ret+=c[pos];
        pos-=lowbit(pos);
    }
    return ret;
}
void add(int pos,int w){
    while(pos<=n){
        c[pos]+=w;
        pos+=lowbit(pos);
    }
}

树状数组 1. 求前缀最大值， 2.单点修改(往大里改)

int ask(int pos){
    int ret=0;
    while(pos>0){
        ret=max(ret,c[pos]);
        pos-=lowbit(pos);
    }
    return ret;
}
void modify(int pos,int w){
    while(pos<=n){
        c[pos]=max(c[pos],w);
        pos+=lowbit(pos);
    }
}

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

for(int i=1;i<=n;i++){ f[i]=ask(a[i]-1)+1; modify(a[i],f[i]); }

2.最长公共子序列

a 1 4 5 2 3
b 1 5 2 4 3

1 5 2 3

1) 前…个元素
f[i][j] a串前i个元素，b串前j个元素的LCS长度
a[i] != b[j] f[i][j] <- f[i-1][j] f[i][j-1]
a[i] == b[j] f[i][j] <- f[i-1][j-1]+1

O(1)*O(n^2)

f[n][m]

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

2) 以…结尾

f[i][j] a串以i结尾，b串以j结尾的LCS长度

a[i] != b[j] f[i][j] = 0
a[i] == b[j] f[i][j] <- f[k][l] (k

O(n^2)*O(n^2)

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(a[i]!=b[j]) f[i][j]=f[i-1][j];
        else{
            f[i][j]=1;
            for(int k=1;kif(b[k]max(f[i][j],f[i-1][k]+1);
            }
        }
    }

}

int mx[];
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){ // LIS 树状数组优化 
        mx[j] = ask(b[j]-1);
        modify(b[j],f[i-1][j]);
    }
    for(int j=1;j<=m;j++){// LCS
        if(a[i]!=b[j]) f[i][j]=f[i-1][j];
        else{
            f[i][j]=mx[j]+1;
        }
    }
}

//By Menteur_Hxy
#include
#include
using namespace std;

const int MAX=3010;
int n,m,top;
int a[MAX],b[MAX],f[MAX][MAX];

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
// scanf("%d",&m);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        int maxn=0;
        for(int j=1;j<=n;j++) {
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];
            else f[i][j]=maxn+1;
            if(a[i]>b[j]) maxn=max(maxn,f[i-1][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[n][i]);
    printf("%d",ans);
    return 0;   
}

if(f[i+1][j]>f[i+1][j+1]){
 f[i][j]=f[i+1][j]+a[i][j];
 g[i][j]=j;
}else{
 f[i][j]=f[i+1][j+1]+a[i][j];
 g[i][j]=j+1;
}