最长上升子LIS序列详解---nlogn算法+n^2算法求长度及序列本身+洛谷导弹拦截例题

本文主要是介绍最长上升子LIS序列详解---nlogn算法+n^2算法求长度及序列本身+洛谷导弹拦截例题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

emmmm，空口不好说，直接拿洛谷的一道题来说吧！

题目链接https://www.luogu.org/problemnew/show/P1020

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式：
1行，若干个整数（个数 ≤100000）

输出格式：
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例
输入样例#1：
389 207 155 300 299 170 158 65
输出样例#1：
6
2

这个是最长不上升子序列，不过和LIS的想法是一致的。

对于第一个问题就是最长不上升子序列，先来啊n²算法，就是直接枚举for两遍，第一层枚举1到n，第二层枚举1到i：

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

我们的做法就是将第i个元素放到第j个元素后面看能否增加：

for (int i=1; i<=n; i++)
    for (int j=1; j<=i; j++){
        if (a[j]>=a[i]) f[i]=max(f[j]+1,f[i]);
    }

这个是本题的不上升子序列，上升的只要将if (a[j]>=a[i])改成if (a[j]<a[i])就可以了。
接下来继续，我们以上求的是以每个元素的为尾的最长不上升子序列。但我们要找整体的最长不上升子序列。很容易看出它就在这些值中，那么我们只要在第二层for之后加个取最大值就好了：

for (int i=1; i<=n; i++){
    for (int j=1; j<=i; j++){
        if (a[j]>=a[i]) f[i]=max(f[j]+1,f[i]);
    }
    ans=max(ans,f[i]);
}

最后的ans就是我们的第一个答案了，对于第二个问题就是纯粹的贪心了，我们建立一个数组b，b中元素的个数就是系统的个数。

我们将a[i]一个个放入b，如果a[i]小于等于b[1]，那么我们直接更新b[1]的值为a[i]，如果a[i]大于b[1]我们就对b的后面位置查找，如果大于b中的每一个数，那么我们b数组的的b[++len]=a[i]。最后的len就是第二个答案了：

for (int i=1; i<=n; i++) {
	while (a[i]>b[head]) {
		if (!b[head]) b[head]=a[i];
		else head++;
	}
	b[head]=a[i];
	head=1;
}
for (int i=1; b[i]; i++) len++;

接下来就是第一个问题的nlogn算法了：
该算法用到了二分查找这个东西，我们可以手写，当然我比较懒就直接STL套过去了。

我们建立一个数组f。同样的我们将a[i]一个个放入f中，如果a[i]<=f[len]我们直接将a[i]放入f[++len]中，这个比较好理解。但如果a[i]>f[len]呢？先直接给出代码：

f[1]=a[1];
for (int i=2; i<=n; i++) {
	if (f[len]>=a[i]) f[++len]=a[i];
	else {
		int p=upper_bound(f+1,f+1+len,a[i],greater<int>())-f;
		f[p]=a[i];
	}
}

对于a[i]>f[len]的情况我们再f这个数组里面找到第一个大于a[i]的位置，然后将该位置的后一个给替换成a[i]比如：
f=139 130 120 120 119 ；我们的a[i]=127，那么我们就直接找到了130，然后将130后面的120替换成127。
注意：由于STL二分的是默认的上升容器，当我们的容器是下降的时候我们就要重载二分模板，这时候的顺序就是从尾到头而不是从头到尾了。

替换之后长度并没有发生改变所以并不影响当前的最大长度，而我们需要的是越大越优，这样他才能装更多的东西，举个例子：
f=139 130 120 120 119；我们的后面的a=127 125 124 123 122。

按照我们的方法来：先将120替换成127：
f=139 130 127 120 119；a=125 124 123 122。

接下来将120替换成125,119替换成124，这样123和122才能接上来。而这就是最长上升子序列长度的求法，相信大家也发现了，这个f数组并不是最长上升子序列本身，他只是等价于最长上升子序列长度而已，比如对于首先我们给出的：
f=139 130 120 120 119 ；之后的a[i]=127，将120替换后：
f=139 130 127 120 119；如果之后再也没有了呢？

emmm，所以我们得重新思考，但事实上我们很容易知道f数组的最后一个值一定是准确的，也就是说我们拿着最后一个值直接反推回去就好了，我们从最后一个值反推回去，如果请值满足f[i-1].id<f[i].id那么我们就直接保存该值，否则的话我们一定能在数组a中下标小于f[i].id中找到满足条件的。我们从f[i].id往下找，找到第一个大于f[i].val的看看它的标记的长度是否为i-1就好了（这里我们和n²算法一样标记每个数的最大不上升子序列长度），然后替换掉f[i-1]，接下来就是循环操作了。。。。emmm，口胡一下，没有实际操作，不对请留言。。。

以下是本题的（最上面的洛谷例题）AC代码：

#include <bits/stdc++.h>
using namespace std;
const int mac=1e5+10;
int a[mac],b[mac],f[mac]={0};
int main()
{
	//freopen("ppp.txt","r",stdin);
	int k=1;
	while (scanf ("%d",&a[k])!=EOF){
		k++;
	}
	k--;
	int n=k,head=1,num=0,ans=0,len=1;
	f[1]=a[1];
	for (int i=2; i<=n; i++){
		if (f[len]>=a[i]) f[++len]=a[i];
		else {
			int p=upper_bound(f+1,f+1+len,a[i],greater<int>())-f;
			f[p]=a[i];
		}
	}
	for (int i=1; i<=n; i++){
		while (a[i]>b[head]){
			if (!b[head]) b[head]=a[i];
			else head++;
		}
		b[head]=a[i];
		head=1;
	}
	for (int i=1; b[i]; i++) num++;
	cout<<len<<endl<<num<<endl;
	return 0;
 } 

这篇关于最长上升子LIS序列详解---nlogn算法+n^2算法求长度及序列本身+洛谷导弹拦截例题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！