VKNIGHTS - Quân mã

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=105;
      r:array[0..7] of longint=(0,1,1,2,1,2,2,3);
      p:array[1..3] of longint=(1,2,4);
var n,re,res:longint;
    a:array[1..maxn] of byte;
    g:array[1..maxn,0..7,0..7] of longint;
    f:array[1..maxn,0..7,0..7,0..3*maxn] of longint;
    d,e:array[0..7,0..7] of byte;

function out(x,y:longint):boolean;
begin
     out:=(y<>(x or y));
end;

procedure rf;
var i,j:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     for i:=1 to n do readln(a[i]);
     fillchar(d,sizeof(d),0);
     for i:=0 to 7 do
         for j:=0 to 7 do
         begin
              if not(out(1,i) or out(4,j)) then
              begin
                   d[i,j]:=1;
                   d[j,i]:=1;
              end;
              if not(out(4,i) or out(1,j)) then
              begin
                   d[i,j]:=1;
                   d[j,i]:=1;
              end;
              if not(out(1,i) or out(2,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
              if not(out(2,i) or out(1,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
              if not(out(2,i) or out(4,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
              if not(out(4,i) or out(2,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
         end;
     close(input);
end;

function check(i,j:longint):boolean;
begin
     check:=(a[i]=0) or out(p[a[i]],j);
end;

procedure pr;
var i,j,k,l,t,lt:longint;
begin
     fillchar(f,sizeof(f),0);
     fillchar(g,sizeof(g),0);
     for i:=0 to 7 do
     begin
          if check(1,i) then
          begin
               g[1,i,0]:=r[i]; f[1,i,0,r[i]]:=1;
          end;
     end;
     for i:=2 to n do
     begin
          for j:=0 to 7 do
              for k:=0 to 7 do
                  for l:=0 to 7 do
                      if (d[j,k]=0) and check(i,j) then
                         if (i=2) or (e[j,l]=0) then
                         begin
                              lt:=g[i-1,k,l];
                              t:=lt+r[j];
                              if g[i,j,k]<t then
                                 g[i,j,k]:=t;
                              f[i,j,k,t]:=f[i,j,k,t]+f[i-1,k,l,lt];
                         end;
     end;
     re:=0; res:=0;
     for i:=0 to 7 do
         for j:=0 to 7 do
             if g[n,i,j]>res then res:=g[n,i,j];
     for i:=0 to 7 do
         for j:=0 to 7 do
             re:=re+f[n,i,j,res];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(res,' ',re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download