首先，让我来看看LIS问题

Description

一个数的序列 bi，当 b1 ＜ b2 ＜ ... ＜ bS 的时候，我们称这个序列是上升的。对于给定的一个序列（a1，a2，...，aN），我们可以得到一些上升的子序列（ai1，ai2，...，aiK），这里 1 ≤ i1 ＜ i2 ＜...＜ iK ≤ N。比如，对于序列（1，7，3，5，9，4，8），有它的一些上升子序列，如（1，7），（3，4，8）等等。

这些子序列中最长的长度是 4，比如子序列（1，3，5，8）。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

Format

Input

输入的第一行是序列的长度 N（1 ≤ N ≤ 1000）。

第二行给出序列中的 N 个整数，这些整数的取值范围都在 0 到 10000。

Output

最长上升子序列的长度。

Samples

输入数据 1

7

1 7 3 5 9 4 8

Copy

输出数据 1

4

基础方法求解：

当我们求1~n的LIS长度时，我们可以轻松的发现可以从以前的状态转移过来

经典的动态规划问题！！
于是我们开始设置状态
我们设表示从以结尾的最长子序列长度

注意初始化：
时间复杂度是

Code:

#include<bits/stdc++.h>

using namespace std;

int n,a[10005],dp[10005],ans;

int main(){

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i];

	for(int i=1;i<=n;i++){

		dp[i]=1;

		for(int j=1;j<i;j++)

			if(a[j]<a[i])

				dp[i]=max(dp[i],dp[j]+1);

		ans=max(dp[i],ans);

	}

	cout<<ans;

	return 0;

}

优化

当甚至更大，复杂度的代码肯定会超时

考虑优化？

我们注意到，第二层枚举的时候，会枚举很多无用的状态
比如：当我们枚举到 时，完全没有必要枚举，所以我们可以考虑优化
我们使用贪心策略：当我们枚举的更小的时候，就更有可能和形成更长的子序列
因此，我们可以单调维护前面所有可以考虑转移的数字！

二分（话说什么奇奇怪怪的优化都是他）

新建一个数组， 表示最长上升子序列长度为的时候最大值
我们保证数组存的是最大值的最小值
比如有两个序列
,
最长子序列长度是3，但是存的是5（保证最小）
如何维护这个数组呢？
两种情况
当>[当前最长LIS长度]，我们就更新最长长度，把a[i]接到后面去
当[当前最长LIS长度]时，我们就更新呗
我们注意定义（ 表示最长上升子序列长度为的时候的最小值）
我们能做什么？
不就是更新最小值吗？
又因为数组是单调递增的（这个应该都知道吧）
所以我们二分数组，找到第一个大于等于 的值，更新即可
最后我们输出即可（如果觉得懵的话，可以自己举个例子看看）
时间复杂度是：

Code:

#include<bits/stdc++.h>

using namespace std;

int n,m,a[100005],ans[100005],len;

int erfen(int sum){

	int l=1,r=len,mid;

	while(l<=r){

		mid=(l+r)/2;

		if(ans[mid]>=sum)

			r=mid-1;

		else

			l=mid+1;

	}

	return l;

}

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

		cin>>a[i];

	len=1;

	ans[1]=a[1];

	for(int i=2;i<=n;i++){

		if(a[i]>ans[len])

			ans[++len]=a[i];

		else{

			int pos=erfen(a[i]);

			ans[pos]=a[i];

		}

	}

	cout<<len<<endl;

	return 0;

}

考虑再次优化？

当有些题目时间卡得非常紧的情况下，二分过大的常数可能导致超时，需要再次优化

我们注意这条式子，发现我们第二层的任务是找前的LIS的最长长度

这种修改需要进行单点修改，考虑使用树状数组进行优化

设表示以i结尾的最长上升子序列长度

我们将原数组从小到大排序，并记录他原来的下标（有点像二分），设他为数组

我们遍历到时，找到~的最大值，然后对这个值+1进行更新

时间复杂度是：

注意：如果不去重，就会成为最长不下降子序列

Code:

#include<bits/stdc++.h>

using namespace std;

struct node{int value,num;}a[30005];

int n,t[30005],b[30005],maxx;

bool cmp(node x,node y){

	return x.value<y.value;

}

int lowbit(int x){

	return x&(-x);

}

int ask(int x){//查找t1~tx的最大值

	 int res=-1e9;

	 for(;x;x-=lowbit(x))

	 	res=max(res,t[x]);

	return res;

}

void modify(int x,int r){//更新这个点的最大值

	for(;x<=n;x+=lowbit(x))

		t[x]=max(t[x],r);

}

void solve(){

	for(int i=1;i<=n;i++){

		int x=ask(a[i].num);

		modify(a[i].num,++x);

		maxx=max(maxx,x);

	}

}

int main(){

	cin>>n;

	for(int i=1;i<=n;i++)

		cin>>b[i];

	for(int i=1;i<=n;i++)

		a[i].value=b[i],a[i].num=i;

	sort(a+1,a+1+n,cmp);

	solve();

	cout<<maxx;

	return 0;

}

(如果想了解树状数组，请到我的另一篇博客去咯loolook)

单看着干嘛？还不去写代码？？？？！！！

LIS求解（包括优化）的相关教程结束。