[C++知识库]P1439 【模板】最长公共子序列|C++

最长公共子序列：

经典的做法如下

#include <stdio.h>
#include <iostream>
#pragma warning(disable:4996);
using namespace std;

//最长公共子序列，就是如果相等的话就等于f[i-1][j-1]+1,不相等的话就在f[i-1][j]和f[i][j-1]中取最大的
const int maxn = 1010;
int seq1[maxn];
int seq2[maxn];
int f[maxn][maxn] = { 0 };
int n;
int main()
{
	scanf("%d", &n);
	fill(f[0], f[0] + maxn * maxn, 0);
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &seq1[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &seq2[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (seq1[i] == seq2[j])
			{
				f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]);
			}
			else {
				f[i][j] = max(max(f[i-1][j],f[i][j-1]), f[i][j]);
			}
		}
	}
	printf("%d", f[n][n]);
}

在这道题中，会被卡时间

1s只能运算1e7次，n2的复杂度，数据量又是1e5，肯定会超时间的。

前面那个模板可以直接套，这个解法的话就是比较巧妙了，利用了这比较的序列都是1-n的全排列的性质。

//最长公共子序列，可以用第一个序列中的值进行排列，然后给第二个子序列创建新的序列
//最后问题转换成求最长上升子序列
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996);
using namespace std;

const int maxn = 100010;
int n;
map<int, int> mp;
int seq2[maxn];

int main()
{
	scanf("%d", &n);
	int num;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &num);
		mp[num] = i;
	}
	//第二轮
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &num);
		seq2[i] = mp[num];
	}
	//求最长上升子序列
	int len = 1;
	int up[maxn];
	up[len] = seq2[1];
	for (int i = 2; i <= n; i++)
	{
		if (seq2[i] > up[len])
		{
			up[++len] = seq2[i];
		}
		else {
			int loc = upper_bound(up+1,up+len,seq2[i],less<int>()) - up;
			up[loc] = seq2[i];
		}
	}
	printf("%d", len);
}