链接
传送门
题意
给出一个长度为\(n\)的字符串，输出要将它变成回文串所需要添加字母数目的最小值和任意一个转换之后的回文串。
思路
区间dp。定义状态\(dp[i][j]\)为把从i到j连续子串变为回文串，所需添加字母数目的最小值。有如下转移：
- 当\(s[i] == s[j]\)时，\(dp[i][j] = dp[i + 1][j - 1]\)；
- 当\(s[i] != s[j]\)时，\(dp[i][j] = min(dp[i + 1][j]， dp[i][j - 1]) + 1\)。
至于打印结果，可以直接递归打印。
代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
char s[maxn];
int dp[maxn][maxn];
int DP(int i, int j) {
if (i >= j) {
return 0;
}
int& k = dp[i][j];
if (k != -1) {
return k;
}
if (s[i] == s[j]) {
return k = DP(i + 1, j - 1);
}
return k = min(DP(i + 1, j), DP(i, j - 1)) + 1;
}
void print(int i, int j) {
if (i > j) {
return;
}
if (i == j) {
putchar(s[i]);
} else {
if (s[i] == s[j]) {
putchar(s[i]);
print(i + 1, j - 1);
putchar(s[j]);
} else if (dp[i][j - 1] >= dp[i + 1][j]){
putchar(s[i]);
print(i + 1, j);
putchar(s[i]);
} else {
putchar(s[j]);
print(i, j - 1);
putchar(s[j]);
}
}
}
int main() {
while (~scanf("%s", s)) {
int len = int(strlen(s));
memset(dp, -1, sizeof dp);
printf("%d ", DP(0, len - 1));
print(0, len - 1);
puts("");
}
return 0;
}
|