2009年1月31日星期六

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

4 条评论:

  1. oakley sunglasses wholesale, http://www.oakleysunglasses-wholesale.us.com/
    ugg boots, http://www.uggbootscheap.eu.com/
    ralph lauren uk, http://www.ralphlaurenoutletuk.org.uk/
    thomas sabo uk, http://www.thomassabos.co.uk/
    michael kors factory outlet, http://www.michaelkorsfactoryoutletonline.com/
    michael kors factory outlet, http://www.michaelkorsfactoryoutlets.in.net/
    michael kors handbags, http://www.michaelkorshandbagsoutletstore.us.com/
    oakley sunglasses, http://www.oakleysunglasseswholesale.in.net/
    oakley, http://www.occhialioakleyoutlets.it/
    oakley sunglasses wholesale, http://www.oakleysunglasseswholesale.us.com/
    tory burch shoes, http://www.toryburchshoesoutlet.com/
    pandora jewelry, http://www.pandorajewelryoutlet.us.com/
    hollister uk, http://www.hollistershirts.co.uk/
    cheap nba jerseys, http://www.nbajerseys.net/
    fitflop, http://www.fitflop.in.net/
    louis vuitton, http://www.borselouisvuittonoutlet.it/
    juicy couture outlet, http://www.juicycoutureoutlet.net/
    coach outlet, http://www.coachoutletus.us/
    oakley sunglasses, http://www.oakley.in.net/
    rolex watches uk, http://www.rolexwatches-uk.co.uk/
    longchamp outlet, http://www.longchampoutlet.name/
    michael kors bags, http://www.michaelkorsbags.uk/
    michael kors outlet, http://www.michaelkors-outlets.us.com/
    ugg boots, http://www.uggbootsclearance.in.net/
    nike air max shoes, http://www.nikeairmaxshoess.co.uk/
    links of london, http://www.linksoflondons.co.uk/
    michael kors outlet, http://www.michaelkorsoutletusa.net/
    designer handbags, http://www.designerhandbags.us.com/
    ray ban sunglasses, http://www.raybansunglass.co.uk/
    1003maoqiuyun

    回复删除

 
Creative Commons License
除非另有声明,本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。