「UVA 11404」Palindromic Subsequence-DP

给出一个字符串,输出其字典序最小的最长回文子序列。

链接

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
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「UVA 11404」Palindromic Subsequence 18-10-2017
* DP
* @author xehoth
*/
#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;
}
# DP

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×