POJ 1159 Palindrome（LCS）

题目大意：给定一串字符，添加最少的字符，使之成为回文串。

Sample Input

5

Ab3bd

Sample Output

2

分析：这道题目之前有做过，就是将原字符串逆序得到另一个字符串，求它们的最长公共子序列，这样就能求得它的可以构成回文的最长字符数，用n减去即为添加最少可使之成为回文的数目。

可恨的是之前一直超内存，看了别人的解题报告，原来定义dp[MAX][MAX]时，不用int型，而是short型，内存只占int的一半（见上一篇日志）

另外逆序字符串可以不用新开一个数组，也可以直接在原数组上从后往前循环。

代码如下：

 # include<stdio.h>

 # include<string.h>

 #define MAX 5005

 int max(int a,int b,int c){

     int temp;

     temp = a>b ? a :b;

     return temp>c ?temp :c ;

 }

 char s[MAX],t[MAX];

 short dp[MAX][MAX];    //定义的类型为short

 int main(){

     int i,j,n;

     while(scanf("%d",&n)!=EOF){

         scanf("%s",s);

         for(i=;i<n;i++)

             t[i] = s[n-i-];

         t[n] = ;

         memset(dp,,sizeof(dp));

         for(i=;i<=n;i++){

             for(j=;j<=n;j++){

                 if(s[i-] == t[j-])

                     dp[i][j] = dp[i-][j-] + ;

                 dp[i][j] = max(dp[i][j],dp[i-][j],dp[i][j-]);

             }

         }

         printf("%d\n",n-dp[n][n]);

     }

     return ;

 }

另一种方法：dp[i][j]表示从第i个字符到第j个字符能构成的回文添加的最少字符。

 #include <stdio.h>

 #define Min(a,b) (a<b?a:b)

 const int MAX = ;

 char ch[MAX];

 short dp[MAX][MAX]={};

 int main()

 {

     int lenth, i, j;

     while(scanf("%d%s",&lenth, ch+)!=EOF)

     {

         for(i=lenth;i>;i--)    //自底向上

         {

             for(j=i+;j<=lenth;j++)

             {

                 if(ch[i]==ch[j]){

                     dp[i][j] = dp[i+][j-];

                 }

                 else{

                     dp[i][j] = Min(dp[i+][j],dp[i][j-])+;

                 }

             }

         }

         printf("%d\n",dp[][lenth]);

     }

     return ;

 }

可是在某些变态的OJ里，上面的方法仍然不能AC，这是需要引入滚动数组优化空间，比如在第一种方法之上

代码如下：

 # include<stdio.h>

 # include<string.h>

 #define MAX 5005

 int max(int a,int b,int c){

     int temp;

     temp = a>b ? a :b;

     return temp>c ?temp :c ;

 }

 char s[MAX],t[MAX];

 short dp[2][MAX];

 int main(){

     int i,j,n;

     while(scanf("%d",&n)!=EOF){

         scanf("%s",s);

         for(i=;i<n;i++)

             t[i] = s[n-i-];

         t[n] = ;

         memset(dp,,sizeof(dp));

         for(i=;i<=n;i++){

             for(j=;j<=n;j++){

                 if(s[i-] == t[j-])

                     dp[i%][j] = dp[(i-)%][j-] + ;

                 dp[i%][j] = max(dp[i%][j],dp[(i-)%][j],dp[i%][j-]);

             }

         }

         printf("%d\n",n-dp[n%][n]);

     }

     return ;

 }

巴特西

POJ 1159 Palindrome（LCS）

最新文章

热门文章