LIS——最长递增子序列问题

最长递增子序列，举一个例子：

A={5，6，7，4，2，8，3},它的最长递增子序列是5，6，7，8.

转载一下大佬写的吧，大佬写的真的好，好好学习一下，认真体会：https://blog.csdn.net/ltrbless/article/details/81318935

真题实战：http://lx.lanqiao.cn/problem.page?gpid=T73。

这个题我们要知道一点：

最少下降子序列的个数（最少的拦截系统）=最长不下降子序列的长度（重点）

我采取的dp做法，所以就用dp来讲讲：

#include
 using namespace std;
 int dp[2010];//统计可以最多可以拦截多少导弹
 int up[2010];//统计最少几台拦截装置 
 int ans,cnt;//分别对应上面 
 int a[2010],n;
 int main()
 {
 	ios::sync_with_stdio(false);
 	while(1)
	{
		scanf("%d",&a[n++]);
		char b=getchar();
		if(b=='\n')
		break;
	}
	for(register int i=0;i

　　对于上面问题的证明罗勇军老师的书里已经有严格证明，膜拜大佬就完事了