PKU1159-Palindrome

題目：http://poj.org/problem?id=1159
給一長度不超過5000的字串，
問至少要加幾個字元，才能讓這個字串變成回文


程式碼：http://codepad.org/VXQexJix
(Discuss裡面也有個殊途同歸、很有意思的DP)
原字串和倒置字串的LCS，就是「不用改就能構成迴文的部分」
剩下沒辦法變成LCS的部分，勢必只能在相應位置補上一樣的字元
故答案=字串長度 - LCS長度

2011.12.19後記：
這是2000年北京IOI的題目
約莫十幾年前的老題目了
整個解題基礎就是一個LCS，介紹動態規劃不得不教的題目
其實就跟其他資奧題目、甚至數奧物奧的題目一樣
都是簡單的知識、短暫的時間、精妙的延伸

我很好奇這題在當年是什麼樣難度的問題呢？我想是比較容易吧

難題的解法總是那麼清楚、深刻，令人深深著迷

如果給我機會來教高一解題的話
我想，把整個重心都放在基礎算法的精神上，是不錯的選擇
好比說解釋Dijkstra和BellmanFord的不同？
為什麼一個不能負權一個可以？
是什麼本質上的差別導致了這樣的結果？

但是高中社團因為體質的緣故，一年社員馬上就是一年幹部
(對學術社團來說嫌少了點…)
這種程度的觀察我想不是能在他們升高二以前輕易培養的
高二也是旅途的延伸，也還在摸索答案呢！