ACM-ICPC寒假算法训练3：动态规划2：最长递增子序列 & 最长公共子序列 & 最长公共子串

本文主要是介绍ACM-ICPC寒假算法训练3：动态规划2：最长递增子序列 & 最长公共子序列 & 最长公共子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

也是小良的博客，之前写过了就不写重复的了

题1：HDUOJ 1257 最少拦截系统（有坑）

算法分析：

这个题目我wa了3发……确实有点坑，我们来细品……
这个题目说，第一发炮弹可以达到任意的高度，只是后面的炮弹不得高于这个高度，问依次来n枚导弹，最少需要多少个拦截系统来拦截这些导弹

第一次误解：

我一开始以为，一个拦截系统，没有时效性，第一次的炮弹击落了第一个导弹之后，后面的导弹如果高度低于前一个，那么还可以继续用这个系统，但是如果高于前一个，则需要增加一个系统，那么根据样例：
8
389 207 155 300 299 170 158 65
我们需要两个拦截系统：
第一个系统：389 207 155
第二个系统：300 299 170 158 65
当时心想，这TM也忒简单了吧！
然后五行代码提交……wa的无地自容

正解：

构造出一个反例：
8
7 6 5 6 3 2 4 1
如果按照第一个思路，就应该输出3，如下：
第一个系统：7 6 5
第二个系统：6 3 2
第三个系统：4 1
但是，别人告诉我（哎，我又理解错题意了）：这样应该输出2
因为导弹高度为4的可以被第一个系统击落，因为4小于5，然后1可以被第二个系统击落，因为1小于2……好坑啊

重新整理思路：

每次输入一个导弹的高速，我们都应该去扫一遍已知系统的当前高度，然后去寻找合适的一个系统去拦截，如果没有这样的系统，则需要重新增加一个系统。
那么什么系统是合适的系统呢？首先，必然这个系统的当前高度要不低于这个导弹的高度，不然就无法拦截，其次，如果有多个系统满足条件，我们应该怎么选取呢？

贪心策略：

再次看这个样例：
8
389 207 155 300 299 170 158 65
系统调度：
第一个系统：
389 207 155
第二个系统：
300 299 170 158

然后 65 这个导弹应该放到哪里去呢？显然这个导弹的高度，可以由系统2或者系统1去拦截，假设使用系统2拦截，则第二个系统的高度变成：65，第一个系统高度是155，如果此时再来一个导弹，高度是157，则无法实施拦截，只能再增加一个系统，但是如果是把65交给第一个系统拦截，则两个系统的高度为：65 158，这样就可以很好的拦截可能出现的：157高度的导弹，所以我们贪心的策略就是：
选择在满足可以拦截的系统中，当前高度最小的那一个，因为要维护最强拦截系统

AC代码：

#include <cstdio>

const int maxn = 1e4 + 5;
int n, h[maxn], boom;
int main(){
	while(~scanf("%d", &n)){
		int cnt = 1;
		scanf("%d", &boom);
		h[cnt] = boom; n--;
		while(n--){
			scanf("%d", &boom);
			int pos = 0, val = 30005, isVis = 0;
			for(int i = 1;i <= cnt;i++){
				if(boom <= h[i]){
					if(val > h[i]){
						val = h[i];
						pos = i;
						isVis = 1;
					}
				}
			}
			if(isVis)
				h[pos] = boom;
			else
				h[++cnt] = boom;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

另一个思路：最长递增子序列

实际上是在玩最长不增子序列，是LIS的应用，再看那个样例：
8
389 207 155 300 299 170 158 65
首先设置一个标记数组：vis[] = {0};
然后跑一遍最长不增子序列：
序列1：389 300 299 170158 65，然后他们都标记成已经被访问
序列2：207 155

再看看那个坑例子：
8
7 6 5 6 3 2 4 1
序列1：7 6 5 3 2 1
序列2：6 4

我们发现，貌似最长不增子序列的方法更优秀！

但是，它的实现是比较困难的， 因为我们需要跑很多次最长不增子序列，还需要去检查，直到所有数据都被访问（所有导弹都被拦截）

新思路：这个比较难想，我也是看书知道的

观察样例中的第一个最长不增子序列：
X{389，300，299，170，158，65}

Y{207，155}

我们可以发现：
在Y中必然至少有一个数a比X中某个数大，否则Y中的所有数都比X中的数小，这样的话，Y中这个数a就应该在X中。那么如果顺着看，求最长递增子序列，每个不增子序列都能且只能提供一个元素，于是最长递增子序列的规模即是答案。

原因是：
对于任意两个最长不增子序列的集合，都满足我上述的性质，所以假设有两枚导弹 x，y 来自同一个拦截系统，则 x > y 于是与递增违背

AC代码：

#include <cstdio>

const int maxn = 1e4 + 5;
int n, h[maxn];
int LIS(){
	int ans = 1, dp[maxn];
	dp[1] = 1;
	for(int i = 2;i <= n;i++){
		int MaxVal = 0;
		for(int j = 1;j < i;j++)
			if(h[j] < h[i] && MaxVal < dp[j])
				MaxVal = dp[j];
		dp[i] = MaxVal + 1;
		if(dp[i] > ans)
			ans = dp[i];
	}
	return ans;
}

int main(){
	while(~scanf("%d", &n)){
		for(int i = 1;i <= n;i++)
			scanf("%d", &h[i]);
		printf("%d\n", LIS());
	}
	return 0;
}

如何求一个序列的最长递增子序列？

算法1：复用最长公共子序列

已知序列：389 207 155 300 299 170 158 65
排好序： 65 155 158 170 207 299 300 389

最长公共子序列：155 170 或 155 158 等等

所以得出结论：
排好序的序列和原序列的最长公共子序列就是最长递增子序列

求最长公共子序列状态转移方程：

if a[i] = b[j]
	dp[i][j] = dp[i - 1][j - 1] + 1;
else
	dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

LCS代码：

#include <iostream>
#include <algorithm>
using namespace std;

int LCS(int a[], int b[], int n){
	int dp[100][100] = {0}, ans = 0;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if(a[i] == b[j])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			if(dp[i][j] > ans)
				ans = dp[i][j];
		}
	}
	return ans;
}

int main(){
	int n, a[100] = {0}, b[100] = {0};
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	cout << LCS(a, b, n);
	return 0;
}

算法二：求最长递增子序列

设状态：dp[i]是以第 i 个元素结尾的最长递增子序列
则状态转移：dp[i] = max(0, dp[j]) + 1; 1 <= j < i && a[j] < a[i];
意思就是，只要前面的序列有比你小的元素，下标为 j ，那么你当前的状态就可以由 dp[j]转移得到，然后遍历所有你之前的状态，取最优子结构作为你的上一个状态去转移即可。

核心LIS代码：

int LIS(){
	int ans = 1, dp[maxn];
	dp[1] = 1;
	for(int i = 2;i <= n;i++){
		int MaxVal = 0;
		for(int j = 1;j < i;j++)
			if(h[j] < h[i] && MaxVal < dp[j])
				MaxVal = dp[j];
		dp[i] = MaxVal + 1;
		if(dp[i] > ans)
			ans = dp[i];
	}
	return ans;
}

最长递增子序列再优化：单调栈+二分搜索

我们维护一个单调栈，但是与一般单调栈问题处理的方式不一样，我们遇到失去单调性的元素的时候，我们用二分法（因为栈内元素单调）去栈内查找最优的替换策略，什么替换策略是最优的呢？自然是替换在不破坏单调性的情况下，能够替换的最大的数，这个数就是在栈中，比它大的最小的数，这个大家细细品味。因为这样替换之后，整个当前序列的数值下降最大，只有当前数值减少，后面才能加入更多的数。

#include <iostream>
using namespace std;

const int maxn = 1e5 + 5;
int n, a, Stack[maxn], cnt;

int main(){
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a;
		if(a > Stack[cnt] || !cnt)
			Stack[++cnt] = a;
		else{
			int l = 1, r = cnt;
			while(l <= r){
				int mid = (r + l) >> 1;
				if(a <= Stack[mid]) // 搜索第一个出现的比 a 大的数，也就是比a大的最小的数 
					r = mid - 1;
				else
					l = mid + 1;
			}
			Stack[l] = a; // 用 a 替换！ 
		}
	}
	cout << cnt << endl; 
	return 0;
}

子串和子序列有什么区别？？？
子序列可以不连续，但是子串务必要连续！所以子串的状态转移方程就在子序列的基础上稍微修改即可：

if(a[i] == b[j])
	dp[i][j] = dp[i - 1][j - 1] + 1;
else
	dp[i][j] = 0;

这篇关于ACM-ICPC寒假算法训练3：动态规划2：最长递增子序列 & 最长公共子序列 & 最长公共子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！