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

 

 

題意：給出一個字符串，問要將這個字符串變成回文串要添加最少幾個字符
思路：先求出正反串的最長公共子序列，然後剩下的兩邊加上就ok了。（以最長公共子序列為中心）

這裡特別注意1000以上都需要要滾動數組，應該不然會超內存的。

 

 

#include
#include
#include
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<