本篇包含题目：code[vs] 2188 最长上升子序列    code[vs] 1576 最长严格上升子序列

DP思想：

状态：dp[i]表示以第i个数为结尾的最长上升子序列长度。
阶段：按下标划分阶段。这样只会从左往右转移。
状态转移方程：
dp[i] = max(dp[i], dp[j]+1);(j < i && num[j] < num[i])

时间复杂度为O(n^2)。

codevs 2188 最长上升子序列

题目描述 Description

LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？
给出一个长度为N整数序列，请求出它的包含第K个元素的最长上升子序列。
例如：对于长度为6的序列<2,7,3,4,8,5>，它的最长上升子序列为<2,3,4,5>，但如果限制一定要包含第2个元素，那么满足此要求的最长上升子序列就只能是<2,7,8>了。

输入描述 Input Description

第一行为两个整数N,K，如上所述。
接下来是N个整数，描述一个序列。

 输出描述 Output Description

请输出两个整数，即包含第K个元素的最长上升子序列长度。

样例输入 Sample Input

8 6
65 158 170 299 300 155 207 389

样例输出 Sample Output

4

数据范围及提示 Data Size

80%的数据，满足0<n<=1000，0<k<=n
100%的数据，满足0<n<=200000，0<k<=n

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int num[210005], g[210005];
const int inf = 23333333;
int main()
{
	int n, k;
	cin>>n>>k;
	for(int i = 1;i <= n;i ++)
		scanf("%d", &num[i]);
	for(int i = 1;i <= n;i ++)
		g[i] =inf;
	for(int i = 1;i <= n;i ++)
	{
		int j = lower_bound(g+1, g+n+1, num[i])-g;
		if((num[i] <= num[k] && i <= k) || (num[i] > num[k] && i > k))
			g[j] = num[i];
	}
	int ans, maxx = -1;
	for(int i = n;i >= 1;i --)
	{
		if(g[i] > maxx && g[i] != inf)
		{
			maxx = g[i];
			ans = i;
		}
	}
	cout<<ans;
	return 0;
}

codevs 1576 最长严格上升子序列

题目描述 Description

给一个数组a1, a2 … an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。
输出长度即可。

输入描述 Input Description

第一行，一个整数N。
第二行 ，N个整数（N < = 5000）

输出描述 Output Description

输出K的极大值，即最长不下降子序列的长度

样例输入 Sample Input

5
9 3 6 2 7

样例输出 Sample Output

3

【样例解释】

最长不下降子序列为3,6,7

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int num[23333], dp[23333];
int main()
{
	int n;
	cin>>n;
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d", &num[i]);
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++)
	{
		dp[i] = 1;
		for(int j = 1;j < i;j ++)
		{
			if(num[j] < num[i])
				dp[i] = max(dp[i], dp[j] + 1);
			ans = max(dp[i], ans);
		}
	}
	cout<<ans<<endl;
	return 0;
}