char.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 124 行

{
ID:maigoak1
PROG:char
}

program char_recognition;
const
  maxn=1200;
var
  fin,fout:text;
  font:array[1..540,1..20]of boolean;
  dif:array[1..maxn,1..540]of byte;
  img:array[1..maxn-18,19..21]of char;
  bad:array[1..maxn-18,19..21]of integer;
  ans:array[17..maxn]of string[63];
  cor:array[1..maxn]of integer;
  n,i,j,t:integer;
  s:string;
function ch(n:byte):char;
  begin
    if n=0 then ch:=' ' else ch:=chr(96+n);
  end;
procedure recog(s,l:integer);
  var
    c:byte;
    i,x:integer;
  procedure update;
    begin
      if x=bad[s,l] then begin
        if img[s,l]<>ch(c) then
          img[s,l]:='?';
        end
      else if x<bad[s,l] then begin
        if x>120 then
          img[s,l]:='?'
        else
          img[s,l]:=ch(c);
        bad[s,l]:=x;
      end;
    end;
  begin
    bad[s,l]:=maxint;
    for c:=0 to 26 do
      case l of
        19:begin
             x:=0;
             for i:=1 to 19 do
               inc(x,dif[s-1+i,c*20+i]);
             update;
             for i:=19 downto 1 do begin
               x:=x-dif[s-1+i,c*20+i]+dif[s-1+i,c*20+i+1];
               update;
             end;
           end;
        20:begin
             x:=0;
             for i:=1 to 20 do
               inc(x,dif[s-1+i,c*20+i]);
             update;
           end;
        21:begin
             x:=0;
             for i:=1 to 20 do
               inc(x,dif[s-1+i,c*20+i]);
             update;
             for i:=20 downto 1 do begin
               x:=x-dif[s-1+i,c*20+i]+dif[s+i,c*20+i];
               update;
             end;
           end;
      end;
  end;
begin
  assign(fin,'font.in');
  reset(fin);
  readln(fin);
  for i:=1 to 540 do begin
    readln(fin,s);
    for j:=1 to 20 do
      font[i,j]:=s[j]='1';
  end;
  close(fin);

  assign(fin,'char.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do begin
    readln(fin,s);
    for j:=1 to 540 do begin
      dif[i,j]:=0;
      for t:=1 to 20 do
        if font[j,t]<>(s[t]='1') then inc(dif[i,j]);
    end;
  end;
  close(fin);

  for i:=19 to 21 do begin
    for j:=1 to n-i+1 do
      recog(j,i);
    ans[i]:=img[1,i];
    cor[i]:=bad[1,i];
  end;

  for i:=22 to 37 do
    ans[i]:='';

  for i:=38 to n do begin
    ans[i]:='';cor[i]:=maxint;
    for j:=19 to 21 do
      if ans[i-j]<>'' then begin
        t:=cor[i-j]+bad[i-j+1,j];
        if t<cor[i] then begin
          ans[i]:=ans[i-j]+img[i-j+1,j];
          cor[i]:=t;
        end;
      end;
  end;

  assign(fout,'char.out');
  rewrite(fout);
  writeln(fout,ans[n]);
  close(fout);
end.