【動態規劃】IOI2000 回文詞

Title: 回文詞

Input: palin.in

Output: palin.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【问题描述】
    迴文詞是一種對稱的字元串——也就是說，一個迴文詞，從左到右讀和從右到 左讀得到的結果是一樣的。任意給定一個字元串，通過插入若干字元，都可以變成一個迴文 詞。你的任務是寫一個程序，求出將給定字元串變成迴文詞所需插入的最少字元數。 比如字元串“Ab3bd”，在插入兩個字元後可以變成一個迴文詞(“dAb3bAd” “Adb3bdA”)。然而，插入兩個以下的字元無法使它變成一個迴文詞。


【输入格式】
   
     文件的第一行包含一個整數N，表示給定字元串的長度(3≤N≤5000)。

文件的第二行是一個長度為N的字元串。字元串僅由大寫字母“A”到“Z”，小寫字母“a” 到“z”和數字“0”到“9”構成。大寫字母和小寫字母將被認為是不同的。

【输出格式】
   文件只有一行，包含一个整数，表示需要插入的最少字符数。
【输入输出样例】
  文件只有一行，包含一個整數，表示需要插入的最少字元數。
輸入：

palin.in

5

Ab3bd

輸出：

palin.out

2

【分析】
一開始我只拘泥於“字符串兩邊對稱”，不知道該如何DP。
其實，要構成『回文詞』，回到它的定義就行了，即“正著讀和反著讀一樣”。
首先，先把原串反向構成新串，再在新串、原串中求最長公共子序列一樣即可。
最終答案就是(L*2-M*2)/2即L-M。L是原串/新串的長度，M是最長公共子序列長度。

PS.找到了一個講解更好的文章，給上連結！
http://www.worlduc.com/blog.aspx?bid=707178

【我的代碼】
裸代碼RawCode

C++语言: Codee#25422

01 /*
02 *Problem: IOI2000 回文詞
03 *Author: Yee-fan Zhu
04 *Method:Dynamic Programming
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 #include <cstring>
09 #define openfile(str) freopen(str".in","r",stdin),freopen(str".out","w",stdout)
10 #define clr(arr,val) memset(arr,val,sizeof(arr))
11 #define max(a,b) a>b?a:b
12 using namespace std;
13 const int MAXN=5001;
14
15 short int F[MAXN][MAXN];
16 char str1[MAXN],str2[MAXN];
17 int N;
18
19 void init()
20 {
21     scanf("%d\n",&N);
22     clr(str1,'\0'),clr(str2,'\0');
23     int c;
24     for(int i=1;i<=N;i++)
25     {
26         c=getchar();
27         str1[i]=c;
28         str2[N+1-i]=c;
29     }
30     return;
31 }
32
33 void dynamic()
34 {
35     //int Max=0;
36     for(int i=1;i<=N;i++)
37     {
38         for(int j=1;j<=N;j++)
39         {
40             if(str1[i]==str2[j])
41                 F[i][j]=F[i-1][j-1]+1;
42             else
43                 F[i][j]=max(F[i-1][j],F[i][j-1]);
44             //Max=max(Max,F[i][j]);
45         }
46     }
47     printf("%d\n",N-F[N][N]);
48 }
49
50 int main()
51 {
52     openfile("palin");
53     init();
54     dynamic();
55     return 0;
56 }