目录
最长上升子序列
给出一个⻓度为n的数字序列 ai，我们需要找到一个最⻓的子序列， 使得子序列中的数字大小单调递增。 例如： n=5，原序列为 (1,4,2,3,5)，那么我们选择 (1,2,3,5)是最优的。
一、朴素做法 O(2n)
容易想到的朴素做法是枚举所有合法的子序列，计算最⻓的⻓度。用搜 索来实现，从前往后，判断每个数字是否大于当前的序列头部的数字， 然后枚举选或不选，分别递归。复杂度 O(2n)。 如何优化呢？我们回忆：dp的核心思想是减少重复状态的计算。在搜索 的过程中，我们重复计算了大量相同的前缀子序列，如果能够将它们的 答案记录下来，就可以大大减少复杂度。 同时注意到：如果一个序列的头部已经确定了，那么就不会受之后选择 的数字的影响，从而有无后效性和子问题最优性。
设 f(i)表示以 ai作为头部（序列中最后一个）的LIS的⻓度。由于ai 可以接在所有比它小的数字后面，我们得到转移方程
f(i)=maxj<i,aj<ai{f(j)}+1
初始条件为 f(0)=0
二、优化做法 O(nlogn)
注意到在转移的过程中，我们需要反复地从 1∼i中寻找满足 aj<ai的 j，并找到最大的 f(j)。这一过程可以被抽象为从区间中寻找最大值的问 题。 于是，我们以数字的值为下标，建立线段树（树状数组），每次计算f(i) 时直接从 1∼ai−1的区间中找到最大值，然后用 f(i)的值来更新线段 树中以 ai为下标的值。 结合离散化，复杂度可以优化为 O(nlogn)。
没看懂的话我再解释一下优化的策略，这里根据转移方程我们需要满足的两个条件是 j<i和aj<ai，所以用树状数组来维护这两个条件，首先树状数组维护最大值，满足了 aj<ai,然后再正序循环，先用树状数组查询当前 i 前面的最大值，再更新，满足了 j<i，将整个问题的时间复杂度降低到 O(nlogn)。
当然除了可以用树状数组来压缩到 O(nlogn)，也可以用二分来做。
下面这道题目我将给出三种做法及超详细注释的代码：朴素的 O(2n)、树状数组的 O(nlogn)和二分的 O(nlogn)。相信您一看代码就懂了
三、例题引入：P1020 导弹拦截（求最长上升子序列和最长不上升子序列）
第一问：最长不上升序列；第二问：最长上升序列；
具体的证明过程比较麻烦我不会 ，其实只需要自己算一组数据，把样例的数据写下来自己模拟一遍就很清楚了。
1.朴素做法暴力 O(n2)
第一问是求最长不上升子序列，利用dp的思想，我们设 f[i] 为以第 i 个数为开头的最长不上升子序列的长度，需要倒序。
第二问是求最长上升子序列，利用dp的思想，我们设 f[i] 为以第 i 个数为结尾的最长上升子序列的长度，需要正序。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
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,ans1,ans2,f[N],a[N];
int main()
{
while(scanf("%lld",&a[++n])!=EOF);//先输入数据，注意最后一个输入非法才结束，n会多1
n--;//所以要--；
/*最长不上升子序列*/
//因为要求的是不上升子序列，所以后一个必须小于等于前一个，所以先求前面的再更新后面的
for(int i=n;i>=1;--i)//因为它是以i开头的最长不上升子序列，所以这里要从n开始循环,必须倒序
{
f[i]=1;//以第i个数开头的最长不上升子序列的长度至少为1（它本身）
for(int j=i+1;j<=n;++j)
if(a[j]<=a[i])//不上升，所以后面的要小于等于前面的数
f[i]=max(f[i],f[j]+1);
ans1=max(ans1,f[i]);
}
/*最长上升子序列*/
for(int i=1;i<=n;++i)//同上，因为它是以i结尾的最长上升子序列，所以这里要从前往后，正序前面的数推后面的数
{
f[i]=1;
for(int j=1;j<i;++j)
if(a[j]<a[i])//上升，所以前面的数要小于后面的数
f[i]=max(f[i],f[j]+1);//记得一定要+1
ans2=max(ans2,f[i]);
}
printf("%lld\n%lld\n",ans1,ans2);
return 0;
}
2.树状数组优化 O(nlogn)
要注意
最长上升子序列是不能等于的，后面要大于前面，所以要正序，并且查询的时候要-1来保证只会小于不会等于
最长不上升子序列是可以等于的，其实就是求小于等于，所以后面的要小于等于前面的，由于树状数组维护的是最大值（大于等于），而这里要的是小于等于，所以要倒序。
要注意这里要用maxn也就是a数组里的最大值来作为树状数组的上限
因为树状数组里存的就是a数组的值，并维护其最大值
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
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,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;
}
3.二分优化 O(nlogn)
#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register
using namespace std;
const int N=100010;
int a[N],d1[N],d2[N],n;
inline bool read(int &x) {
char c=getchar();
if(c==EOF)return false;
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9') {
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return true;
}
int main() {
while(read(a[++n]));n--;
R int len1=1,len2=1;
d1[1]=d2[1]=a[1];
for(R int i=2; i<=n; i++) {
if(d1[len1]>=a[i])d1[++len1]=a[i];
else *upper_bound(d1+1,d1+1+len1,a[i],greater<int>())=a[i];
if(d2[len2]<a[i])d2[++len2]=a[i];
else *lower_bound(d2+1,d2+1+len2,a[i])=a[i];
}
printf("%d\n%d",len1,len2);
return 0;
}
四、P4309 [TJOI2013]最长上升子序列
考虑每新加进来一个数, 要么答案还是之前的, 要么这个数重新更新一个
发现数是按顺序插入的, 也就是说一个数无论放在哪里, 它后面的数对它都没
有影响
于是我们可以用平衡树之类的东西先把原序列搞出来
然后按位置插入当前位置的值, 更新当前的DP值
然后发现这里可以直接用vector代替平衡树
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
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;
vector<ll>v;
ll ans[N],tree[N];
inline void update(ll k,ll val)//维护最大值的树状数组，解决LIS问题
{
while(k<=N)
{
tree[k]=max(tree[k],val);
k+=k&(-k);
}
}
inline ll query(ll k)
{
ll res=0;
while(k)
{
res=max(tree[k],res);
k-=k&(-k);
}
return res;
}
int main()
{
scanf("%lld",&n);
ll t;
over(i,1,n)
{
scanf("%lld",&t);
v.insert(t+v.begin(),i);
}
ll now;
over(i,0,n-1)
{
now=v[i];
ans[now]=query(now)+1;
update(now,ans[now]);
}
over(i,1,n)
{
ans[i]=max(ans[i],ans[i-1]);
printf("%lld\n",ans[i]);
}
return 0;
}
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号