求调(或许是LIS写错了……)

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

Chizuru_Ichinose @ 2023-11-16 20:32:50


#include<bits/stdc++.h>
using namespace std;
const int kMax=1e5+5;
int n;
int l1[kMax],l2[kMax],Te[kMax],F[kMax],ans;
int main(){
    //Lcs--LIS
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l1[i];
    for(int i=1;i<=n;i++) cin>>l2[i];
    //预处理
    for(int i=1;i<=n;i++){
        Te[i]=l1[i];
        l1[i]=i;
    }
    for(int i=1;i<=n;i++) l2[i]=Te[l2[i]];
    /*
    for(int i=1;i<=n;i++) cout<<l1[i]<<" ";
    cout<<'\n';
    for(int i=1;i<=n;i++) cout<<l2[i]<<" ";
    */
    //LIS
    ans=0;
    for(int i=1;i<=n;i++) F[i]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            int m=0;
            if(F[j]>m && l2[i]>=l2[j]) m=F[j];
            F[i]=m+1;
            if(F[i]>=ans) ans=F[i];
        }
    }
    cout<<ans;
    return 0;
}

|