POJ 1159-Palindrome(dp_回文串+滾動數組)

POJ 1159-Palindrome(dp_回文串+滾動數組)

Palindrome Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status

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

題意：讓你在原串裡面添加最少的字母個數使原串變成回文串。

思路：最少補充的字母個數=原序列的長度-原串和逆串的最長公共子串的長度。dp儲存的是從i到j的相同字母的個數。

PS：因為5000*5000肯定超內存，所以在這裡引入滾動數組的知識。滾動數組很適合用在二維ＤＰ而且是數組在很大時，可以節省內存，消除超內存的隱患！

滾動數組講解

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int inf=0x3f3f3f3f;

char str1[5010];
char str2[5010];
int dp[2][5010];
int main()
{
    int n,i,j;
    while(~scanf("%d",&n)){
        getchar();
        for(i=1;i<=n;i++){
            scanf("%c",&str1[i]);
            str2[n-i+1]=str1[i];
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            if(str1[i]==str2[j])
                dp[i%2][j]=dp[(i-1)%2][j-1]+1;
            else
                dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
        }
        printf("%d\n",n-dp[n%2][n]);
    }
    return 0;
}