现在的位置: 首页 > 综合 > 正文

poj2817

2018年01月15日 ⁄ 综合 ⁄ 共 1460字 ⁄ 字号 评论关闭

【题意】

将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.
【上篇】
【下篇】

抱歉!评论已关闭.