【题意】
将n个字符串任意顺序任意位置排列,求对应位置相同字母最多有多少个
【输入】
多组数据
每组数据第一行一个数n
接下来n行每行一个字符串
数据以n=0结束
【输出】
对于每组数据
输出一个数字表示答案
状压dp
因为n很小,所以可以用二进制表示每个字符串是否用过
program poj2817; var n,i,j,k,l,count,o:longint; tot:array [0..1] of longint; dl,last:array [0..1,0..1024] of longint; square:array [0..11,0..11] of longint; s:array [0..11] of string; f:array [0..1024,0..11] of longint; function max (a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min (a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin repeat readln(n); if n=0 then break; for i:=1 to n do begin readln(s[i]); while s[i][length(s[i])]=' ' do delete(s[i],length(s[i]),1); end; fillchar(square,sizeof(square),0); for i:=1 to n do for j:=1 to n do for k:=1 to length(s[i]) do begin count:=0; for l:=1 to length(s[j]) do if k+l-1>length(s[i]) then break else if s[i][k+l-1]=s[j][l] then inc(count); if square[i,j]<count then square[i,j]:=count; end; o:=0; fillchar(f,sizeof(f),0); for i:=1 to n do begin inc(tot[o]); dl[o,tot[o]]:=1 shl (i-1); last[o,tot[o]]:=i; end; for j:=1 to n do begin o:=1-o; tot[o]:=0; for i:=1 to tot[1-o] do for k:=1 to n do if dl[1-o,i] or (1 shl (k-1)) <> dl[1-o,i] then if f[dl[1-o,i] or (1 shl (k-1)),k]< f[dl[1-o,i],last[1-o,i]]+max(square[last[1-o,i],k],square[k,last[1-o,i]]) then begin if f[dl[1-o,i] or (1 shl (k-1)),k]=0 then begin inc(tot[o]); dl[o,tot[o]]:=dl[1-o,i] or (1 shl (k-1)); last[o,tot[o]]:=k; end; f[dl[1-o,i] or (1 shl (k-1)),k]:=f[dl[1-o,i],last[1-o,i]] +max(square[last[1-o,i],k],square[k,last[1-o,i]]); end; end; count:=0; for i:=1 to n do if f[(1 shl n)-1,i]>count then count:=f[(1 shl n)-1,i]; writeln(count); until false; end.