PKU ACM 1159-Palindrome

題目來源：http://acm.pku.edu.cn/JudgeOnline/problem?id=1159

解題報告：

求一個字元串中至少添加幾個字元可以使該字元串變成回文串。也是一道簡單的DP，我這裡用了備忘錄的方法，f[i][j]表示要使字元串的第i個到第j個間的字元串成為回文串至少需要添加的字元的個數，那麼有兩種情況：

第一種，a[i]=a[j]，那麼f[i][j]=f[i+1][j-1]

第二種，a[i]!=a[j]，那麼f[i][j]=min(f[i+1][j], f[i][j-1])+1,

對于f[][]，我一開始設了一個f[5001][5001]，結果報Memory Limit Exceed，于是，我改用動态數組，另外注意到，f[i][j]中j<i的情況是用不到的，是以重新設定，令f[i][j-i]代表原來的f[i][j]，那麼最後隻需要N+(N-1)+...+1=(N+1)*N/2個數，原來則需要N*N個數。再重新送出就AC了。

#include <iostream>

using namespace std;

int **f;

int min(int a,int b)

{

return a>b?b:a;

}

int value(char a[], int begin, int end)

{

if(begin>end)

return 0;

if(f[begin][end-begin]!=-1)

return f[begin][end-begin];

if(begin==end)

f[begin][end-begin]=0;

else

{

if(a[begin]==a[end])

f[begin][end-begin]=value(a,begin+1,end-1);

else

f[begin][end-begin]=1+min(value(a,begin+1,end),value(a,begin,end-1));

}

return f[begin][end-begin];

}

int main()

{

int N;

cin >> N;

char *a=new char[N];

f=new int *[N];

for(int i=0;i<N;i++)

f[i]=new int [N-i];

for(int i=0;i<N;i++)

cin >> a[i];

for(int i=0;i<N;i++)

{

for(int j=i;j<N;j++)

{

f[i][j-i]=-1;

}

}

cout << value(a,0,N-1) << endl;

}

附錄：

Palindrome

Time Limit: 3000MS	Memory Limit: 65536K
Total Submissions: 29519	Accepted: 9874

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