(字符串的处理4.7.16)POJ 1159 Palindrome(让一个字符串变成回文串需要插入多少个字符...先逆序,在减去公共子序列的最大长度即可

 
 * POJ_1159.cpp 
 * 
 *  Created on: 2013年10月29日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
#include <cmath>  
#include <algorithm>  
#include <cstring>  
  
  
using namespace std;  
  
const int maxn = 5005;  
char str1[maxn],str2[maxn];  
int maxlen[2][maxn];  
  
int main(){  
    int n;  
    while(cin >> n ){  
        memset(maxlen,0,sizeof(maxlen));  
  
        scanf("%s",str1);  
  
        int i,j;  
        int len = strlen(str1);  
        for(i = 0 ; i < len ; ++i){  
            str2[i] = str1[n-1 -i];//str2为str1的逆序串  
        }  
  
        int e = 0;  
        for(i = 0 ; i < n ; ++i){//求公共子序列的最大长度  
            e = 1- e;//这里使用了滚动数组,因为直接开maxlen[5000][5000]会内存溢出...  
            for(j = 0 ; j < n ; ++j){  
                if(str1[i] == str2[j]){  
                    maxlen[e][j] = maxlen[1-e][j-1] + 1;  
                }else{  
                    maxlen[e][j] = max(maxlen[1-e][j],maxlen[e][j-1]);  
                }  
            }  
        }  
  
        cout<<n - maxlen[e][n-1]<<endl;  
    }  
  
    return 0;  
}

补充：软件开发 , C++ ,