POJ 1159 Palindrome（最长公共子序列）

题意：

给出一个字符串，计算最少要插入多少个字符可以使得该串变为回文串。

思路：

计算出最长公共子序列，再用原长-LCS=所要添加的字符数。

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 5000 + 5;
 9 
10 char s1[maxn], s2[maxn];
11 int n;
12 int d[2][maxn];
13 
14 int main()
15 {
16     //freopen("D:\txt.txt", "r", stdin);
17     while (~scanf("%d", &n))
18     {
19         int e = 0;
20         scanf("%s", s1+1);
21         //逆串
22         for (int i = 1; i <= n; i++)
23             s2[n - i + 1] = s1[i];
24         memset(d, 0, sizeof(d));
25         for (int i = 1; i <= n; i++)
26         {
27             e = 1 - e;
28             for (int j = 1; j <= n; j++)
29             {
30 
31                 if (s1[i] == s2[j])
32                     d[e][j] = d[1 - e][j - 1] + 1;
33                 else
34                     d[e][j] = max(d[1 - e][j], d[e][j - 1]);
35             }
36         }
37         cout << n - d[e][n] << endl;
38     }
39 }