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
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 
优化 
当甚至更大，复杂度的代码肯定会超时
 考虑优化？ 
我们注意到，第二层枚举的时候，会枚举很多无用的状态
比如：当我们枚举到 时，a[i])"  src="https://latex.codecogs.com/gif.latex?j%28j%3Ci%2Ca%5Bj%5D%3Ea%5Bi%5D%29" />完全没有必要枚举，所以我们可以考虑优化
我们使用贪心策略：当我们枚举的更小的时候，就更有可能和形成更长的子序列
因此，我们可以单调维护前面所有可以考虑转移的数字！
二分（话说什么奇奇怪怪的优化都是他） 
新建一个数组， 表示最长上升子序列长度为的时候最大值
我们保证数组存的是最大值的最小值
比如有两个序列
,
最长子序列长度是3，但是存的是5（保证最小）
如何维护这个数组呢？
两种情况
当>[当前最长LIS长度]，我们就更新最长长度，把a[i]接到后面去
当[当前最长LIS长度]时，我们就更新呗
我们注意定义（ 表示最长上升子序列长度为的时候的最小值）
我们能做什么？
不就是更新最小值吗？
又因为数组是单调递增的（这个应该都知道吧）
所以我们二分数组，找到第一个大于等于 的值，更新即可
最后我们输出即可（如果觉得懵的话，可以自己举个例子看看）
时间复杂度是：
Code: 
#include

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< 
考虑再次优化？ 
 
 当有些题目时间卡得非常紧的情况下，二分过大的常数可能导致超时，需要再次优化
 
 
我们注意这条式子，发现我们第二层的任务是找前的LIS的最长长度
 
 
这种修改需要进行单点修改，考虑使用树状数组进行优化
 
 
设表示以i结尾的最长上升子序列长度
 
 
我们将原数组从小到大排序，并记录他原来的下标（有点像二分），设他为数组
 
 
我们遍历到时，找到~的最大值，然后对这个值+1进行更新
 
 
时间复杂度是： 
 
 
注意：如果不去重，就会成为最长不下降子序列
 
Code: 
 
#include
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>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< 
(如果想了解树状数组，请到我的另一篇博客去咯loolook) 
 
 单看着干嘛？还不去写代码？？？？！！！