Vijos 1327 回文词 解题报告

很Orz的一题，由于没想到什么好的优化，只好写了个O(n^2)的DP交上去，同一个程序交了3次才AC……

看了一下题解，没看到什么更好的方法，所以还是写写我的RP算法吧……用f[i,j]表示从第i位起j个字母的子串要成为回文词最少需要添加的字符数，于是可得到一个和LCS有点像的状态转移方程，f[i,j]=f[i+1,j-2](s[i]=s[i+j-1]),min(f[i,j-1],f[i+1,j-1])+1(s[i]<>s[i+j-1])。由于f[i]只与f[i+1]有关，所以可以利用滚动数组将空间复杂度降到O(n)。

R1126951 Accepted 100 From IwfWcf－ P1327 FPC Vijos Dolphin 2009-1-31 16:02:32