模板 - 最长上升子序列与最长公共子序列

整理的算法模板合集： ACM模板

---

目录

1.最长上升子序列（LIS）1.1树状数组优化$O(nlogn)$ 2.最长公共子序列（LCS）2.1转换成LIS优化$O(nlogn)$

1.最长上升子序列（LIS）

给出一个⻓度为n的数字序列$ai$，我们需要找到一个最⻓的子序列， 使得子序列中的数字大小单调递增。 例如：$n=5$，原序列为$(1,4,2,3,5)$，那么我们选择$(1,2,3,5)$是最优的。

1.1树状数组优化$O(nlogn)$

最长上升子序列是不能等于的，后面要大于前面，所以要正序，并且查询的时候要-1来保证只会小于不会等于

最长不上升子序列是可以等于的，其实就是求小于等于，所以后面的要小于等于前面的，由于树状数组维护的是最大值（大于等于），而这里要的是小于等于，所以要倒序。

要注意这里要用maxn也就是a数组里的最大值来作为树状数组的上限

因为树状数组里存的就是a数组的值，并维护其最大值

ll n,m,ans1,ans2,tree[N],a[N],maxn; inline void update(ll k,ll val)//更新 { while(k<=maxn)//要注意这里是maxn也就是a数组里的最大值来作为树状数组的上限 { tree[k]=max(tree[k],val);//维护最大值 k+=k&(-k); } } inline ll query(ll k) { ll res=0; while(k) { res=max(res,tree[k]);//求以小于等于x的数为结尾的最长不上升子序列的长度的最大值 k-=k&(-k); } return res; } int main() { while(scanf("%lld",&a[++n])!=EOF)maxn=max(maxn,a[n]); n--; for(int i=n;i>=1;--i) { ll q=query(a[i])+1; /*相当于朴素做法的：for(int j=i+1;j<=n;j++) if(a[j]<=a[i]) 因为是按照顺序从后往前循环，所以当前的i所query到的所有的值都是在i后面的， 解决了i<j的问题，树状数组维护最大值，就解决了a[j]<=a[i]的问题， 所以这里求的就是以i为开头的最长不上升子序列的长度*/ update(a[i],q);//这个最大值+1就是以当前这个数开头的最长不上升子序列的长度，丢到树状数组里面去更新后面的值 ans1=max(ans1,q); } memset(tree,0,sizeof tree); for(int i=1;i<=n;++i) { ll q=query(a[i]-1)+1; /*查询以小于（没有等于！！！）x的数为结尾的最长上升子序列的长度的最大值 因为不能等于所以要-1*/ update(a[i],q);//这个最大值+1就是以当前这个数结尾的最长上升子序列的长度，丢到树状数组里面去 ans2=max(ans2,q); } printf("%lld\n%lld\n",ans1,ans2); return 0; }

2.最长公共子序列（LCS）

给出两个⻓度为n的序列$\{a_i\}和\{b_i\}$，求它们的公共子序列的最⻓⻓ 度。 例如两个序列分别为$(1,2,4,8,16)$和$(2,4,6,8,10)$，那么它们的$LCS$就是$(2,4,8)$。

2.1转换成LIS优化$O(nlogn)$

using namespace std; typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A const ll N=100007; const ll INF=1e10+9; const ll mod=2147483647; const double EPS=1e-10;//-10次方约等于趋近为0 const double Pi=3.1415926535897; ll n,m,a[N],b[N],tree[N],mp[N]; inline void update(ll k,ll val)//树状数组维护的是mp数组的值的最大值 { while(k<=N) { tree[k]=max(tree[k],val); k+=k&(-k); } } inline ll query(ll k)//查到的k都是值小于k的节点的最大值，所以就保证了单调性 { ll res=0; while(k) { res=max(res,tree[k]); k-=k&(-k); } return res; } void advanced() { over(i,1,n) mp[b[i]]=i;//mp函数就是一个简单的映射离散化 over(i,1,n)//如果a里有b里没有那么p[a[i]]就是0，树状数组是没办法处理0的所以就不会任何影响 update(mp[a[i]],query(mp[a[i]])+1); printf("%lld\n",query(n)); } int main() { scanf("%lld",&n); over(i,1,n) scanf("%lld",&a[i]); over(i,1,n) scanf("%lld",&b[i]); advanced(); return 0; }