pojPalindrome

思路：

　　反转题目所给的字符串，并与所给字符串求他们两个的最长公共子序列的值。

　　总长减去最长公共子序列的值就是最少安插所需的值。

注意：此题直接建二维数组会爆内存，可以使用滚动数组来优化内存！！！

ac代码：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #define ll long long
 7 #define inf 0x3f3f3f3f
 8 using namespace std;
 9 const int N = 5000 + 10;
10 
11 int dp[2][N];
12 char s1[N], s2[N];
13 
14 int main() {
15 
16     int n;
17     cin >> n;
18     scanf("%s", s1 + 1);
19     for (int i = 1; i <= n; i++) {
20         s2[n + 1 - i] = s1[i];
21     }
22     for (int k = 1, i = 0; k <= n; k++, i ^= 1) {
23         for (int j = 1; j <= n; j++) {
24             dp[i][j] = max(dp[i ^ 1][j], dp[i][j - 1]);
25             if (s1[k] == s2[j]) dp[i][j] = max(dp[i][j], dp[i ^ 1][j - 1] + 1);
26         }
27     }
28     if (n % 2 == 0) {
29         cout << n - dp[1][n] << "\n";
30     }
31     else {
32         cout << n - dp[0][n] << "\n";
33     }
34 
35     return 0;
36 }