Palindrome
| Time Limit: 3000MS |
|
Memory Limit: 65536K |
| Total Submissions: 40443 |
|
Accepted: 13741 |
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
這題跟編輯距離類似
由于自己一點思路也沒有
所以網(wǎng)上找了找題解
方法1：f[i][j]表示從下標(biāo)i到下標(biāo)j最少添加幾個字符構(gòu)成回文
f[i][j]=min(f[i+1][j-1],min(f[i][j-1],f[i+1][j])+1)
方法2：求該串與其反串的最長公共子串的長度，最少添加的次數(shù)就是串長減子串長
我用第二種方法做的
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4#define MAX 5005
5int len,i,j;
6char s[MAX],s1[MAX];
7short f[MAX][MAX];
8int max(int a,int b)
9
{
10
if (a>b) return a; else return b;
11
}
12int main()
13{
14 scanf("%d",&len);
15 scanf("%s",&s);
16 for (i=len-1;i>=0 ;i-- )
17
{
18 s[i+1]=s[i];
19
}
20 for (i=1;i<=len ;i++ )
21 {
22 s1[len-i+1]=s[i];
23 }
24 f[0][0]=0;
25 for (i=1;i<=len ;i++ )
26 {
27 for (j=1;j<=len ;j++ )
28 {
29 if (s[i]==s1[j])
30 {
31 f[i][j]=max(f[i-1][j-1]+1,f[i][j]);
32 }
33 f[i][j]=max(f[i][j],f[i-1][j]);
34 f[i][j]=max(f[i][j],f[i][j-1]);
35 }
36 }
37 printf("%d\n",len-f[len][len]);
38 return 0;
39}
40//當(dāng)前狀態(tài)僅與上一層狀態(tài)有關(guān)，可以用滾動數(shù)組優(yōu)化
41
我寫的比較惡心，沒用的東西太多
Orz大神