算法刷题day49：线性DP—最长上升子序列模型

写完了线性 $DP$ 的十道题之后，我感觉得到了一种升华，今天花了大概七八个小时吧，感觉就是理解的越来越深了，以前都是背过来了，现在能明白有些东西为什么要这样，或者说还可以那样写。尤其是导弹防御的问题，让自己对暴搜和迭代加深的印象也越来越深了， $DP$ 和暴搜其实是一家的，而且要准备蓝桥杯国赛，主要就是准备 $DP$ 和暴搜，图论其后，剩余的就把基础课的东西整明白就行了，然后再针对性的多刷刷题，

XATU-LiJiachang

1189人浏览 · 2024-05-19 17:50:45

XATU-LiJiachang · 2024-05-19 17:50:45 发布

引言

写完了线性 $D P$ 的十道题之后，我感觉得到了一种升华，今天花了大概七八个小时吧，感觉就是理解的越来越深了，以前都是背过来了，现在能明白有些东西为什么要这样，或者说还可以那样写。尤其是导弹防御的问题，让自己对暴搜和迭代加深的印象也越来越深了， $D P$ 和暴搜其实是一家的，而且要准备蓝桥杯国赛，主要就是准备 $D P$ 和暴搜，图论其后，剩余的就把基础课的东西整明白就行了，然后再针对性的多刷刷题，坚持下去，一定不会差，加油！

一、最长上升子序列 I

标签：动态规划、线性DP、最长上升子序列

思路：状态定义： $f [i]$ 代表以 $a [i]$ 为结尾最长上升子序列的长度，那么我们可以根据倒数第二步，将其划分，倒数第二步可能是从 $1\sim i - 1$ 的所有可能，在这么些情况中取一个最大值即可，最后在所有以 $a [i]$ 为结尾的可能中取最大值就是答案。时间复杂度为 $O(N^2)$

题目描述：

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

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

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

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

数据范围
1≤N≤1000，−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 = 1010, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], f[N];

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

二、怪盗基德的滑翔翼

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

思路：由题意得，求的是最长上升和下降子序列的最大长度，跟上一题的做法基本一样，只不过多开了一个新的数组用来记录最长下降子序列的长度，变一下符号即可，详情见代码。

题目描述：

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。

而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出
的足球破坏了。

不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。

初始时，怪盗基德可以在任何一幢建筑的顶端。

他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。

因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。

他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。

请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

输入格式
输入数据第一行是一个整数K，代表有K组测试数据。

每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按
照建筑的排列顺序给出。

输出格式
对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

数据范围
1≤K≤100,1≤N≤100,0<h<10000
输入样例：
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10
输出样例：
6
6
9

示例代码：

#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 = 110, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], f[N], g[N];

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

三、登山

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

思路：肯定存在一个分界点，使得这个分界点之前的景点是最长上升子序列，之后是最长下降子序列，那么我们分别求出来从前到后的最长上升子序列和从后向前的最长上升子序列，然后取和减一求最大值就是所求的答案。

题目描述：

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景
点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式
第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式
输出一个整数，表示最多能浏览的景点数。

数据范围
2≤N≤1000
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
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 = 1010, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], f[N], g[N];

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

四、合唱队形

标签：DP、线性DP、最长上升子序列、前后缀分解

思路：跟上一题的思路简直是一模一样，只不过题目要求的是最少需要几位同学出列，那么变相的是求最多的合唱队形，然后拿总人数减去它就是答案了，最多的合唱队形人数就是上一题的代码，然后拿总人数一减即可。

题目描述：

N 位同学站成一排，音乐老师要请其中的 (N−K) 位同学出列，使得剩下的 K 位同学排成合唱队形。     

合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T1，T2，…，TK，  则他们的
身高满足 T1<…<Ti>Ti+1>…>TK(1≤i≤K)。     

你的任务是，已知所有 N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式
输入的第一行是一个整数 N，表示同学的总数。

第二行有 N 个整数，用空格分隔，第 i 个整数 Ti 是第 i 位同学的身高(厘米)。

输出格式
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

数据范围
2≤N≤100,130≤Ti≤230
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
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 = 110, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], f[N], g[N];

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

五、友好城市

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

思路：我们首先把这些城市的北岸的编号由大到小排好序，然后发现其对应的城市建立航线，要保持不相交的话，就必须保证南岸的城市的编号是严格单调上升的，如果不是，那么肯定会存在一条相交的线，所以做法就是对一边的城市排个序，在此基础上遍历找最长上升子序列。

题目描述：

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以
避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式
第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围
1≤N≤5000,0≤xi≤10000
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
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 = 5010, M = N, INF = 0x3f3f3f3f;

int n, m;
PII segs[N];
int f[N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> segs[i].x >> segs[i].y;
	sort(segs, segs+n);
	
	int res = 0;
	for(int i = 0; i < n; ++i)
	{
		f[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(segs[i].y > segs[j].y) f[i] = max(f[i], f[j]+1);
		}
		res = max(res, f[i]);
	}
	
	cout << res << endl;
	
	return 0;
}

六、最大上升子序列和

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

思路：首先还是要单调上升，只不过 $f [i]$ 的属性变为了值的和而非长度，其实就是初始化变为了 $f [i] = a [i]$ ，然后判断其是可以上升的时候，取最值变为了 $f [i] = ma x (f [i], f [j] + a [i])$ ，从原来的最长变为了最大的和，方法和思考方式其实没有变，变的只是属性罢了。

题目描述：

一个数的序列 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)等等。

这些子序列中和最大为18，为子序列(1,3,5,9)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

输入格式
输入的第一行是序列的长度N。

第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。

输出格式
输出一个整数，表示最大上升子序列和。

数据范围
1≤N≤1000
输入样例：
7
1 7 3 5 9 4 8
输出样例：
18

示例代码：

#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, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], f[N];

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];
	
	int res = 0;
	for(int i = 0; i < n; ++i)
	{
		f[i] = a[i];
		for(int j = 0; j < i; ++j)
		{
			if(a[i] > a[j]) f[i] = max(f[i], f[j]+a[i]);
		}
		res = max(res, f[i]);
	}
	
	cout << res << endl;
	
	return 0;
}

七、拦截导弹

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

思路1：首先第一问求的就是最长不上升子序列的最大长度，直接求就行了。第二问问的就是最少用多少个这么个子序列能够把这些数给覆盖了，做法其实就是求最长上升子序列的个数，因为肯定存在一条最长上升子序列，使得这里面的每一个数都必须要新开一个组来存，所以这是肯定的，也是最少的。

思路2：第一问是一样的，说一下第二问。我们可以用一个数组来存，每一个数代表一个最长不上升子序列的末尾元素，我们可以根据贪心的策略来选择从现有的组里存还是新开一个组，判断依据就是找最接近该元素的组去存，因为这样可以最大程度的“节省空间”，所以我们应该存到一个大于等于该数的最小值的组，如果不存在则新开一个组。首先这样的末尾元素的构成是一个严格单调递增的，我们假设没有元素满足，那就需要新开一个组，因为组的编号肯定是由小到大的，没有元素满足也就是说不存在大于等于该数的末尾元素，所以按照坐标系看，越往右越大，所以是严格单调递增的，然后这样我们可以用二分去找，这里的边界等细节还是很有考究的，详情见代码。

题目描述：

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

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

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

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

输入导弹依次飞来的高度（雷达给出的高度数据是不大于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, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], f[N], g[N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	while(cin >> a[n]) n++;
	
	int res1 = 0, res2 = 0;
	for(int i = 0; i < n; ++i)
	{
		f[i] = g[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(a[i] <= a[j]) f[i] = max(f[i], f[j]+1);
			if(a[i] > a[j]) g[i] = max(g[i], g[j]+1);
		}
		res1 = max(res1, f[i]);
		res2 = max(res2, g[i]);
	}
	
	cout << res1 << endl << res2 << 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, M = N, INF = 0x3f3f3f3f;

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

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	while(cin >> a[n]) n++;
	
	int res = 0;
	for(int i = 0; i < n; ++i)
	{
		f[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(a[i] <= a[j]) f[i] = max(f[i], f[j]+1);
		}
		res = max(res, f[i]);
		
		int l = 0, r = len - 1;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(g[mid] >= a[i]) r = mid;
			else l = mid + 1;
		}
		
		if(len && g[r] >= a[i]) g[r] = a[i];  // 如果有元素并且满足要求
		else g[len++] = a[i];
	}
	
	cout << res << endl << len << endl;
	
	return 0;
}

八、最长上升子序列 II

标签：贪心

思路：由于用传统的方法时间复杂度是 $O(N^2)$ 的，但是这道题的数据范围是 $N\leq 10^5$ ，所以是要超时的，这道题要么用 $O (N)$ 或者 $O(N\cdot logN)$ 的做法才不会超时。这道题采用的跟上一道题有异曲同工之妙，都是用一个数组存该序列的末尾的值，存储的依据也是尽可能的合理利用空间，也就是存储到小于该元素的最大值的后面，不一样的是该数组的编号代表长度，上一题的编号仅仅指的是序列的数量。那么我们得知这个末尾元素组成的序列也是单调上升的，因为如果是非单调上升的话，那么这个最长的元素的倒数第二个元素肯定是小于倒数第一个元素的，那么也就小于上一个长度的最后一个元素，那么上一个长度的序列就不对了，因为存在一个跟它长度相同但是末尾元素比它小的序列，那么就矛盾了。做法也是用二分的思路，找出小于该元素的最大值，值得注意的是，找到了这个序列，那么改变的是下一个序列的末尾元素，因为长度变了。这个边界问题要么直接走到右端点，那么就是右端点也是小于它的，那么长度就为 $r + 1$ ，没什么说呢，如果到了左端点，那么因为这个零号相当于一个哨兵结点，如果没有一个比它小的，那么它就是最小值，那么 $g [1] = 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;  // 有概念可知需要取到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;
}

九、导弹防御系统

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

思路1：该思路采用的是暴搜的情况，就跟那个小猫爬山一样，遍历每一个导弹，该导弹要么加入到上升序列中去，要么加入到下降序列中去。然后具体加入到哪个序列中去跟导弹拦截这道题是一模一样，只不过在此基础上加了个暴搜和下降序列的情况，分析方法是一样的。我这里只说一下，二分的边界条件。首先长度就是具体的含义，但是是从 $0$ 开始的，然后就是因为下降的情况拦截导弹已经说过了，这里说一下上升的情况，那么我们遍历到一个高度，根据节省空间的原则，就得放到小于该数的最大值，如果没有满足要求的，那么所有的数都是大于该数的，那么新开的组的末尾元素就都大于该数，所以这整个序列末尾元素的组成是单调递减的，然后去二分，二分之后，如果有组满足要求就放到组里，如果刚开始没有组或者不满足要求那就新开一个组，这里注意的是回溯回来需要回复现场。

思路2：其实就是把暴搜换成迭代加深了而已，可以看得出迭代加深其实不是很难，就是再原有的基础上加个判断而已。感觉能用迭代加深还是用一下，因为一般情况下都不会变慢，而且还能用IDA*去加速一下。一般 $D FS$ 求最值要么设置一个全局变量，把所有情况全部跑一遍求最值，要么就用迭代加深。迭代加深其实就是判断当前的深度是否有解，因为是从小到大遍历的，所以第一次有解的情况就是最小值。

题目描述：

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

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

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

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

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

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

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

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

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

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

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

示例代码1： dfs+二分

#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, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], up[N], down[N];
int ans = 2e9;

void dfs(int u, int p, int q)
{
	if(p + q >= ans) return;  // 最优性剪枝 
	if(u == n)
	{
		ans = p + q;
		return;
	}
	
	int l = 0, r = p - 1;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(up[mid] < a[u]) r = mid;
		else l = mid + 1;
	}
	
	if(p && up[r] < a[u]) 
	{
	    int t = up[r];
		up[r] = a[u];
		dfs(u+1,p,q);
		up[r] = t;
	}
	else 
	{
		up[p] = a[u];
		dfs(u+1,p+1,q);
	}
	
	l = 0, r = q - 1;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(down[mid] > a[u]) r = mid;
		else l = mid + 1;
	}
	
	if(q && down[r] > a[u]) 
	{
	    int t = down[r];
		down[r] = a[u];
		dfs(u+1,p,q);
		down[r] = t;
	}
	else 
	{
		down[q] = 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)
	{
		ans = 2e9;
		for(int i = 0; i < n; ++i) cin >> a[i];
		
		dfs(0,0,0);
		
		cout << ans << 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 = 55, M = N, INF = 0x3f3f3f3f;

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

bool dfs(int depth, int u, int p, int q)
{
	// 为什么不是大于等于，因为要判断等于的情况是否正确
	if(p + q > depth) return false;  // 最优性剪枝 
	if(u == n) return true;
	
	int l = 0, r = p - 1;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(up[mid] < a[u]) r = mid;
		else l = mid + 1;
	}
	
	if(p && up[r] < a[u]) 
	{
	    int t = up[r];
		up[r] = a[u];
		if(dfs(depth,u+1,p,q)) return true;
		up[r] = t;
	}
	else 
	{
		up[p] = a[u];
		if(dfs(depth,u+1,p+1,q)) return true;
	}
	
	l = 0, r = q - 1;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(down[mid] > a[u]) r = mid;
		else l = mid + 1;
	}
	
	if(q && down[r] > a[u]) 
	{
	    int t = down[r];
		down[r] = a[u];
		if(dfs(depth,u+1,p,q)) return true;
		down[r] = t;
	}
	else 
	{
		down[q] = a[u];
		if(dfs(depth,u+1,p,q+1)) return true;
	}
	
	return false;
}

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];
		
		int depth = 0;
		while(!dfs(depth,0,0,0)) depth++;
		
		cout << depth << endl;
	}
	
	return 0;
}

十、最长公共上升子序列

标签：动态规划、线性DP、前缀和

思路：首先状态定义 $f [i] [j]$ 代表在 $A$ 中 $1\sim i$ 和 $B$ 中 $1\sim j$ 中出现且以 $B [j]$ 结尾的最长公共上升子序列的集合，划分的依据是根据是否包括 $A [i]$ 来确定的，如果不包括那么就是 $f [i - 1] [j]$ ，如果包括首先得 $A [i] = B [j]$ ，然后根据 $0\sim j-1$ 来划分，然后再划分时也要判断其是否为上升子序列，把最大值赋给 $f [i] [j]$ 即可。然后这里的最长值可以直接存起来用，避免了三种循环超时，详情见代码。

题目描述：

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列
的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 A 和 B 的长度均不超过 3000。

输入格式
第一行包含一个整数 N，表示数列 A，B 的长度。

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

第三行包含 N 个整数，表示数列 B。

输出格式
输出一个整数，表示最长公共上升子序列的长度。

数据范围
1≤N≤3000,序列中的数字均不超过 231−1。

输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
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 = 3010, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], b[N];
int f[N][N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n; ++i) cin >> b[i];
	
	for(int i = 1; i <= n; ++i)
	{
		int maxv = 1;
		for(int j = 1; j <= n; ++j)
		{
			f[i][j] = f[i-1][j];
			if(a[i] == b[j])
			{
				int maxv = 1;
				for(int k = 1; k < j; ++k)
				{
					if(b[k] < b[j])
					{
						maxv = max(maxv, f[i-1][k] + 1);
					}
				}
				f[i][j] = max(maxv, f[i][j]);
			}
		}
	}
	
	int res = 0;
	for(int i = 1; i <= n; ++i) res = max(res, f[n][i]);
	
	cout << res << 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 = 3010, M = N, INF = 0x3f3f3f3f;

int n, m;
int a[N], b[N];
int f[N][N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n; ++i) cin >> b[i];
	
	for(int i = 1; i <= n; ++i)
	{
		int maxv = 1;
		for(int j = 1; j <= n; ++j)
		{
			f[i][j] = f[i-1][j];
			if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
			if(b[j] < a[i]) maxv = max(maxv, f[i-1][j] + 1);
		}
	}
	
	int res = 0;
	for(int i = 1; i <= n; ++i) res = max(res, f[n][i]);
	
	cout << res << endl;
	
	return 0;
}