题目描述

给定两个整数序列。编写一个程序，找出它们的最长公共递增子序列。

长度为 N 的序列 S₁, S₂, ..., Sₙ 被称为长度为 M 的序列 A₁, A₂, ..., Aₘ 的递增子序列，如果存在 1 ≤ i₁ < i₂ < ... < iₙ ≤ M，使得对于所有 1 ≤ j ≤ N，有 Sⱼ = Aᵢⱼ，并且对于所有 1 ≤ j < N，有 Sⱼ < Sⱼ₊₁。

输入格式

每个序列的描述包括：

• M —— 序列的长度（1 ≤ M ≤ 500）。
• M 个整数 Aᵢ（-2³¹ ≤ Aᵢ < 2³¹）—— 序列本身。

输出格式

输出的第一行是 L —— 两个序列的最长公共递增子序列的长度。第二行输出该子序列。如果有多个可能的答案，输出其中任意一个。

示例输入 1

5
1 4 2 5 -12
4
-12 1 2 4

示例输出 1

2
1 4

来源

Northeastern Europe 2003, Northern Subregion

题意分析

我们需要找到两个序列的最长公共递增子序列（LCIS）。公共子序列是指在两个序列中都出现的子序列，递增子序列是指元素严格递增的子序列。我们需要找到满足这两个条件的最长子序列。

解题思路

1. 动态规划（Dynamic Programming）：

   • 使用动态规划来解决最长公共递增子序列问题。
   • 定义 dp[i][j] 表示第一个序列前 i 个元素和第二个序列前 j 个元素的 LCIS 长度。
   • 状态转移：
     • 如果 A[i] == B[j]，则 dp[i][j] = max(dp[i-1][k] + 1)，其中 k < j 且 B[k] < B[j]。
     • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
   • 为了优化，可以记录前驱节点以重建子序列。

2. 优化：

   • 使用一维数组优化空间复杂度。
   • 在遍历第二个序列时，维护一个变量 max_len 来记录当前的最大长度。

3. 重建子序列：

   • 通过记录前驱节点或使用额外的数组来存储子序列的元素。

C++代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N = 505;
 
int n, m, a[N], b[N], dp[N][N], path[N][N], out[N], on;
 
int bo = 0;
 
void print(int n, int m) {
    if (n == 0)
	return;
    print(n - 1, path[n][m]);
    if (path[n][m] != m) {
	if (bo) printf(" ");
	else bo = 1;
	printf("%d", b[m]);
    }
}
 
int main() {
    while (~scanf("%d", &n)) {
	bo = 0;
	for (int i = 1; i <= n; i++)
	    scanf("%d", &a[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++)
	    scanf("%d", &b[i]);
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++) {
	    int Max = 0, Maxv = 0;
	    for (int j = 1; j <= m; j++) {
		if (dp[i][j] < dp[i - 1][j]) {
		    dp[i][j] = dp[i - 1][j];
		    path[i][j] = j;
		}
		if (a[i] == b[j]) {
		    if (dp[i][j] < Max + 1) {
			dp[i][j] = Max + 1;
			path[i][j] = Maxv;
		    }
		}
		if (b[j] < a[i]) {
		    if (Max < dp[i - 1][j]) {
			Max = dp[i - 1][j];
			Maxv = j;
		    }
		}
	    }
	}
	int ansv = 1;
	for (int i = 1; i <= m; i++) {
	    if (dp[n][ansv] < dp[n][i]) {
		ansv = i;
	    }
	}
	printf("%d\n", dp[n][ansv]);
	print(n, ansv);
	printf("\n");
    }
    return 0;
}

算法标签

1. 动态规划（Dynamic Programming）
2. 最长公共子序列（Longest Common Subsequence, LCS）
3. 最长递增子序列（Longest Increasing Subsequence, LIS）
4. 序列处理（Sequence Processing）
5. 优化算法（Optimization Algorithms）