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 winsty
program sgu327_sqybi;
const
nn = 14;
mm = 30;
unable = nn * mm * 100;
type
TStr = string[mm];
var
n, i, j, k, rt, best, besti, bestp, t: longint;
res: ansistring;
flag: array[1..nn]of boolean;
a, aa: array[1..nn]of TStr;
r: array[1..nn]of longint;
b: array[1..nn, 1..2, 1..nn, 1..2]of longint;
d: array[1..2 shl nn, 1..nn, 1..2]of longint;
path: array[1..2 shl nn, 1..nn, 1..2, 1..3]of longint;
function include(s1, s2: TStr): boolean;
var
i, j: longint;
f: boolean;
begin
include := false;
if length(s1) < length(s2) then exit;
for i:=1 to length(s1)-length(s2)+1 do begin
f := true;
for j:=1 to length(s2) do
if s1[i+j-1] <> s2[j] then begin
f := false;
break;
end;
if f then begin
include := true;
exit;
end;
end;
end;
function convert(s: TStr): TStr;
var
ss: TStr;
i: longint;
begin
ss := ”;
for i:=1 to length(s) do
ss := s[i] + ss;
convert := ss;
end;
function connect(s1, s2: TStr): longint;
var
t, i, j: longint;
f: boolean;
begin
connect := 0;
if s1 = s2 then exit;
t := length(s1);
for i:=0 to length(s1)-1 do begin
f := false;
for j:=1 to length(s2) do begin
if j + i > length(s1) then begin
f := true;
t := i;
break;
end;
if s2[j] <> s1[j+i] then
break;
end;
if f then break;
end;
connect := length(s2) - (length(s1) - t);
end;
procedure f(x, y, z: longint);
var
i, j, t: longint;
begin
t := x - r[y];
d[x, y, z] := unable;
for i:=1 to n do
if r[i] and t <> 0 then
for j:=1 to 2 do begin
if d[t, i, j] = -1 then f(t, i, j);
if d[x, y, z] > d[t, i, j] + b[i, j, y, z] * 2 then begin
d[x, y, z] := d[t, i, j] + b[i, j, y, z] * 2;
path[x, y, z, 1] := t;
path[x, y, z, 2] := i;
path[x, y, z, 3] := j;
end;
end;
end;
procedure print(x, y, z: longint);
var
i, t: longint;
begin
if path[x, y, z, 1] <> 0 then
print(path[x, y, z, 1], path[x, y, z, 2], path[x, y, z, 3])
else begin
if z = 2 then a[y] := convert(a[y]);
res := a[y];
t := connect(a[y], convert(a[y]));
for i:=t downto 1 do
res := res + a[y][i];
exit;
end;
if z = 2 then a[y] := convert(a[y]);
t := (d[x, y, z] - d[path[x, y, z, 1], path[x, y, z, 2], path[x, y, z, 3]]) div 2;
for i:=t downto 1 do
res := a[y][i] + res;
for i:=t downto 1 do
res := res + a[y][i];
end;
begin
readln(n);
for i:=1 to n do
readln(a[i]);
fillchar(flag, sizeof(flag), true);
for i:=1 to n do
for j:=1 to n do
if i <> j then
if flag[j] and (include(a[j], a[i]) or include(a[j], convert(a[i]))) then begin
flag[i] := false;
break;
end;
k := 0;
for i:=1 to n do
if flag[i] then begin
inc(k);
aa[k] := a[i];
end;
a := aa;
n := k;
if n = 1 then begin
t := connect(a[1], convert(a[1]));
if connect(convert(a[1]), a[1]) < t then begin
t := connect(convert(a[1]), a[1]);
a[1] := convert(a[1]);
end;
write(a[1]);
for i:=t downto 1 do
write(a[1][i]);
writeln;
halt;
end;
r[1] := 1;
for i:=2 to n do
r[i] := r[i-1] shl 1;
rt := 0;
for i:=1 to n do
rt := rt + r[i];
for i:=1 to n do
for j:=1 to n do
if i <> j then begin
b[i, 1, j, 1] := connect(convert(a[i]), convert(a[j]));
b[i, 1, j, 2] := connect(convert(a[i]), a[j]);
b[i, 2, j, 1] := connect(a[i], convert(a[j]));
b[i, 2, j, 2] := connect(a[i], a[j]);
end;
fillchar(d, sizeof(d), -1);
for i:=1 to n do begin
d[r[i], i, 1] := length(a[i]) + connect(a[i], convert(a[i]));
d[r[i], i, 2] := length(a[i]) + connect(convert(a[i]), a[i]);
end;
best := maxlongint;
for i:=1 to n do begin
f(rt, i, 1);
f(rt, i, 2);
if d[rt, i, 1] < best then begin
best := d[rt, i, 1];
besti := i;
bestp := 1;
end;
if d[rt, i, 2] < best then begin
best := d[rt, i, 2];
besti := i;
bestp := 2;
end;
end;
res := ”;
print(rt, besti, bestp);
writeln(res);
end.
阅读(194 次)