1 /*
2 题意：问最少插入多少个字符使得字符串变成回文串
3 区间DP：dp[i][j]表示[l, r]的字符串要成为回文需要插入几个字符串，那么dp[l][r] = dp[l+1][r-1]; (str[l] == str[r])
4 dp[l][r] = min (dp[l+1][r], dp[l][r-1]) + 1，然后按照状态转移递归输出路径
5 */
6 /************************************************
7 * Author :Running_Time
8 * Created Time :2015-8-17 14:42:57
9 * File Name :UVA_10453.cpp
10 ************************************************/
11
12 #include <cstdio>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <cstring>
17 #include <cmath>
18 #include <string>
19 #include <vector>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
26 #include <bitset>
27 #include <cstdlib>
28 #include <ctime>
29 using namespace std;
30
31 #define lson l, mid, rt << 1
32 #define rson mid + 1, r, rt << 1 | 1
33 typedef long long ll;
34 const int MAXN = 1e3 + 10;
35 const int INF = 0x3f3f3f3f;
36 const int MOD = 1e9 + 7;
37 char str[MAXN];
38 int dp[MAXN][MAXN];
39
40 void print(int l, int r) {
41 if (l > r) return ;
42 if (l == r) printf ("%c", str[l]);
43 else if (str[l] == str[r]) {
44 printf ("%c", str[l]);
45 print (l + 1, r - 1);
46 printf ("%c", str[l]);
47 }
48 else if (dp[l][r] == dp[l+1][r] + 1) {
49 printf ("%c", str[l]);
50 print (l + 1, r);
51 printf ("%c", str[l]);
52 }
53 else {
54 printf ("%c", str[r]);
55 print (l, r - 1);
56 printf ("%c", str[r]);
57 }
58 }
59
60 void work(void) {
61 memset (dp, 0, sizeof (dp));
62 int len = strlen (str);
63 for (int i=2; i<=len; ++i) {
64 for (int j=0; j+i-1<len; ++j) {
65 int k = j + i - 1;
66 int &res = dp[j][k] = INF;
67 if (str[j] == str[k]) res = dp[j+1][k-1];
68 res = min (res, min (dp[j+1][k], dp[j][k-1]) + 1);
69 }
70 }
71 printf ("%d ", dp[0][len-1]);
72 print (0, len - 1); puts ("");
73 }
74
75 int main(void) { //UVA 10453 Make Palindrome
76 while (scanf ("%s", str) == 1) {
77 work ();
78 }
79
80 return 0;
81 }
区间DP UVA 10453 Make Palindrome
编译人生，运行世界！