POJ 1159 Palindrome

　　寻找串与其逆串的最长公共子序列。

　　因为此子序列必是回文串，剩下的字符就是需要插入的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 #define Max(a,b) a > b ? a : b
 7 
 8 using namespace std;
 9 
10 char s1[5010],s2[5010];
11 
12 short int CountLen[5010][5010];
13 
14 int main()
15 {
16     int len;
17     while(~scanf("%d",&len))
18     {
19     scanf("%s",(s1+1));
20 
21     int mid = len/2;
22 
23     int i,j;
24 
25     for(j = 1,i = len;i >= 1; --i,++j)
26     {
27         s2[j] = s1[i];
28     }
29 
30     s2[j] = '';
31 
32     for(i = 0;i <= len; ++i)
33     {
34         for(j = 0;j <= len; ++j)
35         {
36             if(i == 0 || j == 0)
37             {
38                     CountLen[i][j] == 0;
39             }
40             else if(s1[i] == s2[j])
41             {
42                 CountLen[i][j] = CountLen[i-1][j-1]+1;
43             }
44             else
45             {
46                 CountLen[i][j] = Max(CountLen[i][j-1],CountLen[i-1][j]);
47             }
48         }
49     }
50 
51 
52     printf("%d
",len-CountLen[len][len]);
53     }
54     return 0;
55 }

View Code

　　用 int 有可能会MLE　可以用short也可以用滚动数组。

　　下面是用滚动数组优化的代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 #define Max(a,b) a > b ? a : b
 7 
 8 using namespace std;
 9 
10 char s1[5010],s2[5010];
11 
12 short int CountLen[2][5010],temp[5010];
13 
14 int main()
15 {
16     int len;
17     while(~scanf("%d",&len))
18     {
19     scanf("%s",(s1+1));
20 
21     int i,j;
22 
23     for(j = 1,i = len;i >= 1; --i,++j)
24     {
25         s2[j] = s1[i];
26     }
27 
28     s2[j] = '';
29 
30     memset(CountLen,0,sizeof(CountLen));
31     memset(temp,0,sizeof(temp));
32 
33     for(i = 0;i <= len; ++i)
34     {
35         for(j = 0;j <= len; ++j)
36         {
37             if(i == 0 || j == 0)
38             {
39                 CountLen[i&1][j] = 0;
40             }
41             else if(s1[i] == s2[j])
42             {
43                 CountLen[i&1][j] = CountLen[(i+1)&1][j-1]+1;
44             }
45             else
46             {
47                 CountLen[i&1][j] = Max(CountLen[i&1][j-1],CountLen[(i+1)&1][j]);
48             }
49         }
50     }
51 
52     printf("%d
",len-CountLen[len&1][len]);
53     }
54     return 0;
55 }

View Code