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
这题跟编辑距离类似
由于自己一点思路也没有
所以网上找了找题解
方法1：f[i][j]表示从下标i到下标j最少添加几个字符构成回文
f[i][j]=min(f[i+1][j-1],min(f[i][j-1],f[i+1][j])+1)
方法2：求该串与其反串的最长公共子串的长度，最少添加的次数就是串长减子串长
我用第二种方法做的
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//当前状态仅与上一层状态有关，可以用滚动数组优化
41
我写的比较恶心，没用的东西太多
Orz大神