子序列问题

最长公共子序列

#include<bits/stdc++.h>
using namespace std;
int dp[200][200];
int lena,lenb,n;
int a[200],b[200];
int main(){
    cin>>n;
    for(register int i=1;i<=n;i++)cin>>a[i];
    for(register int i=1;i<=n;i++)cin>>b[i];
    lena=n;lenb=n;
    for(register int i=1;i<=lena;i++){
        for(register int j=1;j<=lenb;j++){
            if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[lena][lenb];
    return 0;
}

最长上升/下降/不升/不降子序列

#include<bits/stdc++.h>
using namespace std;
int n;
int a[maxn],g[maxn],f[maxn];
int main(){
    cin>>n;
    for(register int i=1;i<=n;i++)cin>>a[i];
    for(register int i=1;i<=n;i++)g[i]=0x3f3f3f3f,f[i]=0;
    int ans=0;
    for(register int i=1;i<=n;i++){
        f[i]=lower_bound(g+1,g+1+ans,a[i])-g;
        g[f[i]]=a[i];
        ans=max(f[i],ans);
    }
    cout<<ans<<endl;
    return 0;
}