QBGAME - Trò chơi trên ma trận

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const maxn=10010;
var b,sl:array[1..60] of longint;
    c:array[1..60,1..60] of longint;
    f:array[0..1,1..60] of int64;
    a:array[0..7,1..maxn] of longint;
    d:array[1..maxn,1..60] of int64;
    num,n,mx:longint;
    oo,re:int64;

function kt(i:longint):boolean;
var j:longint;
begin
     kt:=false;
     for j:=0 to 6 do
         if (i shr j and 1=1) and (i shr (j+1) and 1=1) then exit;
     kt:=true;
end;

procedure init;
var i,j,k,dem:longint;
begin
     oo:=1000000000;
     oo:=oo*oo;
     for i:=0 to 255 do
         if kt(i) then
         begin
              inc(num); b[num]:=i;
         end;
     dem:=0;
     for i:=1 to num-1 do
         for j:=i+1 to num do
             if b[i] and b[j]=0 then
             begin
                  inc(sl[i]);
                  c[i,sl[i]]:=j;
                  inc(sl[j]);
                  c[j,sl[j]]:=i;
             end;
end;

procedure rf;
var i,j:longint;
begin
     read(n); mx:=-maxlongint;
     for i:=0 to 7 do
         for j:=1 to n do
         begin
              read(a[i,j]);
              mx:=max(mx,a[i,j]);
         end;
end;

procedure init2;
var i,j,k:longint;
begin
     for j:=1 to num do
         for k:=0 to 7 do
             if b[j] shr k and 1=1 then
                for i:=1 to n do
                    d[i,j]:=d[i,j]+a[k,i];
end;

procedure pr;
var i,j,k,z:longint;
begin
     if mx<=0 then
     begin
          writeln(mx); exit;
     end;
     init2;
     for j:=1 to num do f[1,j]:=d[1,j];
     for i:=2 to n do
     begin
          z:=i and 1;
          for j:=1 to num do f[z,j]:=-oo;
          for j:=1 to num do
              for k:=1 to sl[j] do
                  f[z,j]:=max(f[z,j],f[1-z,c[j,k]]+d[i,j]);
     end;
     re:=-oo;
     for i:=1 to num do
         re:=max(re,f[z,i]);
     writeln(re);
end;

begin
     init;
     rf;
     pr;
end.

Download