给出一个字符串，输出其字典序最小的最长回文子序列。
链接
UVA 11404
题解
首先考虑如何求出最长回文子序列的长度。
直接把串反转过来，求出两串的 LCS 即可。
然后考虑如何输出方案，一个显然的思路是在做 LCS 的时候，记录下每个状态，然后输出 LCS 即可，然而这样做是有反例的，如
1
2
| kfclbckibbibjccbej
jebccjbibbikcblcfk
|
其 LCS 是 bcibbibc，但它不是回文的。注意到 LCS 的前半部分一定是回文串的前半部分，所以我们直接用前半部分构造出这个回文串就好了，构造的时候要分奇偶讨论一下。
在做 LCS 的时候，用 std::string 记录，理论上应该是 $O(n ^ 3)$，所以需要优化，但此题直接记录刚好能过，换成 __gnu_cxx::__rc_string 快了 $5$ 倍。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <bits/extc++.h>
namespace {
typedef __gnu_cxx::__rc_string String;
const int MAXN = 1000;
char s[MAXN + 1], revs[MAXN + 1];
int f[MAXN + 1][MAXN + 1];
String str[MAXN + 1][MAXN + 1];
inline void solveCase() {
register int len = strlen(s + 1);
std::reverse_copy(s + 1, s + len + 1, revs + 1);
for (register int i = 0; i <= len; i++) f[0][i] = 0, str[0][i].clear();
for (register int i = 1; i <= len; i++) {
for (register int j = 1; j <= len; j++) {
if (s[i] == revs[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
str[i][j] = str[i - 1][j - 1] + s[i];
} else {
if (f[i - 1][j] > f[i][j - 1]) {
f[i][j] = f[i - 1][j], str[i][j] = str[i - 1][j];
} else if (f[i - 1][j] < f[i][j - 1]) {
f[i][j] = f[i][j - 1], str[i][j] = str[i][j - 1];
} else {
f[i][j] = f[i - 1][j];
str[i][j] = std::min(str[i - 1][j], str[i][j - 1]);
}
}
}
}
register int maxLen = f[len][len];
const String &ans = str[len][len];
if (maxLen & 1) {
for (register int i = 0; i < maxLen / 2; i++) std::cout << ans[i];
for (register int i = maxLen / 2; i >= 0; i--) std::cout << ans[i];
std::cout << '\n';
} else {
for (register int i = 0; i < maxLen / 2; i++) std::cout << ans[i];
for (register int i = maxLen / 2 - 1; i >= 0; i--) std::cout << ans[i];
std::cout << '\n';
}
}
inline void solve() {
while (std::cin >> (s + 1)) solveCase();
}
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
solve();
return 0;
}
|
