3月12日 lis lcs 的优化

lis 最长上升子序列的二分优化

最长上升子序列

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,a[100001],b[100001]; // b[i]表示的是长度为i的最长上升子序列的结尾的最小值
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    b[m=1]=a[1];
    for(int i=2;i<=n;i++){
        if(b[m]<a[i]) b[++m]=a[i];
        else{
            //二分查找第一个大于等于a[i]的元素的下标，即l
            l=1,r=m;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(a[i]<=b[mid]) r=mid-1;
                else l=mid+1;
            }
            b[l]=a[i]; //注意：b[l]是一定大于b[l-1]的
        }
    }
    printf("%d",m);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],b[100001];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    b[m=1]=a[1];
    for(int i=2;i<=n;i++){
        if(b[m]<a[i]) b[++m]=a[i];
        else{
            int* it=lower_bound(b+1,b+m+1,a[i]);
            *it=a[i];
        }
    }
    printf("%d",m);
    return 0;
}

lcs 最长公共子序列

最长公共子序列

#include<bits/stdc++.h>
using namespace std;
string a,b;
int ans[1001][1001];
int main(){
    cin>>a>>b;
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=a.length();i++){
        for(int j=1;j<=b.length();j++){
            if(a[i-1]==b[j-1]){
                ans[i][j]=ans[i-1][j-1]+1;
            }else{
                ans[i][j]=max(ans[i-1][j],ans[i][j-1]);
            }
        }
    }
    cout<<ans[a.length()][b.length()];
    return 0;
}

若序列中无重复数据，可通过map记录每个数据的位置，然后用二分优化（怎样优化暂且不提）