1 条题解
-
0
[F] LCS(dp_f)题解
题意简述
给定两个串 ,求一个最长的公共子序列(输出任意一个即可)。
思路
第一步:求长度
设 = 的前 个字符与 的前 个字符的 LCS 长度:
$$f_{i,j} = \begin{cases} f_{i-1,j-1} + 1, & s_i = t_j,\\[2pt] \max(f_{i-1,j},\; f_{i,j-1}), & s_i \ne t_j. \end{cases}$$即 LCS 长度 。
第二步:还原方案
开一个等大的方向数组
dir[i][j],记录转移来自哪里:- 来自左上(
s_i == t_j):dir = 2; - 来自上方 :
dir = 0; - 来自左侧 :
dir = 1。
从 往回走:遇到
dir == 2就把 记入答案并往左上走,否则按方向回退。最后把记录到的字符反转输出。为什么答案不唯一
LCS 可能有多个。例如
axyb、abyxb,axb与ayb都是长度 的 LCS。因此本题是 Special Judge:只要输出字符串是 与 的公共子序列且长度等于 即判对。复杂度
时间 ,空间 (方向数组用
unsigned char,约 9MB)。参考代码
#include <cstdio> #include <string> #include <vector> using namespace std; int main() { static char bs[3005], bt[3005]; scanf("%s %s", bs, bt); string s = bs, t = bt; int n = s.size(), m = t.size(); vector<vector<unsigned char>> dir(n + 1, vector<unsigned char>(m + 1, 0)); vector<int> prev(m + 1, 0), cur(m + 1, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i - 1] == t[j - 1]) { cur[j] = prev[j - 1] + 1; dir[i][j] = 2; } else if (prev[j] >= cur[j - 1]) { cur[j] = prev[j]; dir[i][j] = 0; } else { cur[j] = cur[j - 1]; dir[i][j] = 1; } } swap(prev, cur); fill(cur.begin(), cur.end(), 0); } string ans; int i = n, j = m; while (i > 0 && j > 0) { if (dir[i][j] == 2) { ans += s[i - 1]; i--; j--; } else if (dir[i][j] == 0) i--; else j--; } reverse(ans.begin(), ans.end()); printf("%s\n", ans.c_str()); return 0; }易错点
- LCS 可能为空串(如
a、z),此时要输出一个空行,不能什么都不输出或输出乱码。 - 重建时字符是逆序收集的,必须反转。
- 方向数组用
int会占 36MB(),用unsigned char更稳。 - 别只输出长度;本题要求输出具体字符串。
数据说明
共 16 组:4 组官方样例(含空串答案的
a/z);、 是 的子串、完全无公共字符、 与 互为逆序; 的随机(字符集大小 3 与 26 各一组)、全a、互为反转等大规模组。全部用 SPJ 校验(公共子序列 + 长度等于独立算出的 LCS 长度)。 - 来自左上(
- 1
信息
- ID
- 15
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者