算法学习系列（五十）：最长上升子序列模型（二）

引言

本章内容讲的是最长上升子序列模型的第二种，基本模型还是以最长上升子序列的优化方法是一个思想，其实还是比较的难想的，并且其序列单调性还是要好好的注意一下，只有台下认真琢磨透，并且写的足够熟练那么考场上才会如鱼得水，加油！

一、最长上升子序列 II

标签：贪心

思路：朴素版的最长上升子序列的时间复杂度是 $O(N^2)$ 的，该数据 $N\le 10^5$ ，所以就会超时，就得对其进行优化，采用的是贪心的策略，时间复杂度： $O(N\cdot logN)$。如果一个数列为 $3,1,......$ ，那么能接在 $3$ 的后面的数，就可以接到 $1$ 的后面去，并且 $1$ 还要更好更兼容一些，所以存储 $3$ 就是没有必要的了。我们可以用一个数组来存储长度为下标的上升子序列的最后一个数是多大，那么这个数肯定是越小越好，然后我们遍历一个数的时候，要求以该数结尾的最长上升子序列最长是多少，首先该数可以放在任意结尾小于该数的后面，然后我们需要放在小于 $a[i]$ 的最大值的后面，这相当于是一个节省资源的方法，也就是选择满足条件最接近该数的一个序列。因为长度越长结尾的数就会越大，所以要放到满足条件的最长的后面，就是以 $a[i]$ 为结尾的最长上升子序列的最长值。那么如果放到后面，那么更新的就是下一个长读的结尾元素了。

题目描述：

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

示例代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n;
int a[N];
int g[N], len;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> a[i];
	
	for(int i = 0; i < n; ++i)
	{
		int l = 0, r = len;
		while(l < r)
		{
			int mid = l + r + 1 >> 1;
			if(g[mid] < a[i]) l = mid;
			else r = mid - 1;
		}
		
		g[r+1] = a[i];
		len = max(len, r+1);
	}
	
    cout << len << endl;
	
	return 0;
}

二、拦截导弹

标签：DP、线性DP、最长上升子序列

思路：首先第一问就是求一个最长不上升子序列的最大值，因为数据范围为 $N\le 1000$ ，所以直接拿朴素版的也能过。然后第二问可以简化为至少要多少个不上升子序列才能把有个的序列覆盖掉，这个其实就是求最长上升子序列的个数，因为肯定存在一个最长上升子序列，使得这里面的每一个导弹都必须要新开一个组才能满足条件，所以这是最小的需要满足的组数。还有一种方法，就是一种贪心的策略，就是跟上一题差不多，就是我们只存每一个组的末尾元素的值，首先这个元素值按照长度从小到大肯定是单调递增的，大家可以先假设为递增的，然后插入一个元素看看是否可以维持递增就可以了。然后插入的元素肯定是要大于等于该元素的最小值，相当于找到最接近该数的序列，然后用二分去做即可。上一题求的是上升子序列最长是多少，这题第二问求的是不上升子序列最短是多少，是一个对偶问题。

题目描述：

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

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

输入格式
共一行，输入导弹依次飞来的高度。

输出格式
第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围
雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

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

示例代码1：贪心

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1010;

int n;
int h[N], f[N], g[N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	while(cin >> h[n]) n++;
	
	int r1 = 0, r2 = 0;
	for(int i = 0; i < n; ++i)
	{
		f[i] = g[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(h[i] <= h[j]) f[i] = max(f[i], f[j] + 1);
			else g[i] = max(g[i], g[j] + 1);
		}
		r1 = max(r1, f[i]);
		r2 = max(r2, g[i]);
	}
	
	cout << r1 << endl << r2 << endl;
	
	return 0;
}

示例代码2：贪心做法

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1010;

int n;
int h[N], f[N];
int g[N], cnt;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	while(cin >> h[n]) n++;
	
	int res = 0;
	g[0] = -1;
	for(int i = 0; i < n; ++i)
	{
		f[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(h[i] <= h[j]) f[i] = max(f[i], f[j] + 1);
		}
		res = max(res, f[i]);
		
		int l = 1, r = cnt;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(g[mid] >= h[i]) r = mid;
			else l = mid + 1;
		}
		
		if(g[r] >= h[i]) g[r] = h[i];
		else g[++cnt] = h[i];
	}
	
	cout << res << endl << cnt << endl;
	
	return 0;
}

三、导弹防御系统

标签：搜索、深度优先搜索、DFS、迭代加深、贪心

思路：这道题我们只能暴力枚举了，要么加入到上升子序列里，要么加入到下降子序列里，优化的方法就是只存每个序列的最后一个元素值，插入是一种贪心：插入到上升子序列里小于它的最大值和下降子序列里的大于它的最小值里，单调性分别为单调递减和单调递增，然后用暴搜即可。

题目描述：

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式
输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围
1≤n≤50
输入样例：
5
3 5 2 4 1
0 
输出样例：
2
样例解释
对于给出样例，最少需要两套防御系统。

一套击落高度为 3,4 的导弹，另一套击落高度为 5,2,1 的导弹。

示例代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 55;

int n;
int a[N];
int up[N], down[N];
int ans;

void dfs(int u, int p, int q)
{
	if(p + q >= ans) return;
	if(u == n)
	{
		ans = p + q;
		return;
	}
	
	int k = 0;
	while(k < p && up[k] >= a[u]) k++;
	
	
	if(k < p) 
	{
	    int t = up[k];
	    up[k] = a[u];
	    dfs(u+1,p,q);
	    up[k] = t;
	}
	else 
	{
	    up[k] = a[u];
	    dfs(u+1,p+1,q);
	}
	
	k = 0;
	while(k < q && down[k] <= a[u]) k++;
	
	if(k < q) 
	{
	    int t = down[k];
	    down[k] = a[u];
	    dfs(u+1,p,q);
	    down[k] = t;
	}
	else 
	{
	    down[k] = a[u];
	    dfs(u+1,p,q+1);
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	while(cin >> n, n)
	{
		for(int i = 0; i < n; ++i) cin >> a[i];
		
		ans = n;
		dfs(0,0,0);
		
		cout << ans << endl;	
	}
	
	return 0;
}