SGU 327 — Yet Another Palindrome
很赞的状态压缩DP题目…用d[s={1, 0, 1, 0, ...}, j, k]表示当前选择情况为s,最后一个选的字符串是j,j放在原先字符串的左边/右边(k=1 or 2)的最小长度.每次取出字符串放到以前放好的字符串前面,比如以前凑好的字符串是abcdcba,现在的字符串是dab,那么就把dab接到原先字符串的左边,就是dabcdcbad.预处理b[i, j, k, p],表示第i个字符串接在左边/右边,第k个字符串接在第i个字符串外面的左边/右边时伸出的最小长度.比如字符串i是abc,k是dab,那么b[i, 1, k, 1]就是1(只有一个d伸出来),而b[i, 1, k, 2]就是3(dab都要伸出来,没有重合部分).
细节方面有很多问题,首先是预处理要删除所有包含关系的字符串只保留最长的,这里如果有两个字符串一样长那么我原来的程序就一个都不会保留.还有预处理时,一个字符串自己生成回文串可能有正反两种情况,我搞错了(就是abc可能生成abcba和cbabc).另外输出结果的时候,print过程对于最中间字符串的处理也有些问题.经过hrm的精心调教和我努力的改程序(虽说代码是越改越恶心=.=),这道WA on test 8许久的题目终于AC了…hrm我爱死你了…
嗯…附代码…建议别看…会恶心死的.
{ SGU 327; Yet Another Palindrome - sqybi’s code - 状态压缩DP}//for my winstyprogram sgu327_sqybi; const nn = 14; mm = 30; unable = nn * mm * 100; type TStr = string[mm];
var n, [...]