lis：最长递增子序列
复杂度:$O(nlgn)$
#include<iostream>
#include<cstdio>
using namespace std;
int num[],lis[],res=;
int solve(int x)
{
int a=,b=res;
while(a!=b)
{
int mid=(a+b)/;
if(lis[mid]>=x)
b=mid;
else
a=mid+;
}
return a;
}
int main()
{
int n;
cin>>n;
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
for(int i=;i<=n;i++)
{
if(lis[res]<=num[i])
res++,lis[res]=num[i];
else
lis[solve(num[i])]=num[i];
}
cout<<res<<endl;
return ;
}
lcs：最长公共子序列
复杂度$n\times m$
#include <cstdio>
#include <iostream>
using namespace std;
int dp[][];
int main()
{
string a,b;
while(cin>>a>>b)
{
for(int i=;i<=a.size();i++)
for(int j=;j<=b.size();j++)
{
if(a[i-]==b[j-])dp[i][j]=dp[i-][j-]+;
else dp[i][j]=max(dp[i-][j],dp[i][j-]);
} char path[];
for(int aa=a.size(),bb=b.size(),num=;aa>=&&bb>=;)
{
if(a[aa-]==b[bb-])
{
path[num++]=a[aa-];
aa--,bb--;
}
else
{
if(dp[aa-][bb]>dp[aa][bb-])
aa--;
else bb--;
}
}
cout<<dp[a.size()][b.size()]<<endl;
for(int i=dp[a.size()][b.size()];i>=;i--)
cout<<path[i]<<" ";
cout<<endl;
}
return ;
}
lics： 最长公共上升子序列
复杂度$n\times m$
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=;
int n,m,num1[maxn],num2[maxn],f[maxn];
int lics()
{
for(int i=;i<=m;i++)f[i]=;
int res=;
for(int i=;i<=n;i++)
{
int k=;
for(int j=;j<=m;j++)
{
if(num1[i]==num2[j])
f[j]=max(f[j],k+); if(num2[j]<num1[i])
{
k=max(f[j],k);
}
res=max(res,f[j]);
}
}
return res;
}
int main()
{
int T;
cin>>T;
for(int i=;i<=T;i++)
{
cin>>n;
for(int j=;j<=n;j++)
scanf("%d",&num1[j]);
cin>>m;
for(int j=;j<=m;j++)
scanf("%d",&num2[j]);
cout<<lics()<<endl;
if(i!=T)
puts("");
}
return ;
}