Palindrome（補全回文串+最長公共子序列的應用）hdu1513+poj1159+動态規劃

Palindrome

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4277    Accepted Submission(s): 1462

Problem Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. 

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.  

Input Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

Output Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

Sample Input

5
Ab3bd
        

Sample Output

2
        

Source IOI 2000  

連結：http://acm.hdu.edu.cn/showproblem.php?pid=1513

題意：給出一個字元串，問要将這個字元串變成回文串要添加最少幾個字元

思路：先求出正反串的最長公共子序列，然後剩下的兩邊加上就ok了。（以最長公共子序列為中心）

這裡特别注意1000以上都需要要滾動數組，應該不然會超記憶體的。

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int map[2][5005];//利用滾動數組
string str;
/***
題意：給出一個字元串，問要将這個字元串變成回文串要添加最少幾個字元
思路：先求出正反串的最長公共子序列，然後剩下的兩邊加上就ok了。（以最長公共子序列為中心）
*/
void LCS(int &len1,int &len2)
{
    for(int i=0;i<=len1;i++)
    {
        for(int j=0;j<=len2;j++)
        {
            if(i==0||j==0) {map[i%2][j]=0; continue;}
            if(str[i-1]==str[len2-j]){ map[i%2][j]=map[(i-1)%2][j-1]+1;}
            else if(map[(i-1)%2][j]>=map[i%2][j-1]){ map[i%2][j]=map[(i-1)%2][j];}
            else { map[i%2][j]=map[i%2][j-1]; }
        }
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        cin>>str;
        LCS(n,n);
        int ans=map[n%2][n];
        cout<<n-ans<<endl;
    }
    return 0;
}

/*
5
Ab3bd
6
Ab34bd
5
Abb3f
*/