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

Tác giả: ladpro98

Ngôn ngữ: Pascal

program qbgame;
uses    math;
const   maxN=12345;
        maxV=255;
        fi='';
var     a:array[1..maxN,1..8] of longint;
        bit:array[0..maxV,1..8] of longint;
        cfg,len:array[0..maxV] of longint;
        s:array[0..maxV,1..maxV] of longint;
        sum,f:array[1..maxN,1..maxV] of int64;

        n,d:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for j:=1 to 8 do
        for i:=1 to n do
        read(inp,a[i,j]);
        close(inp);
end;

function getbit(n,i:longint):longint;
begin
        exit(n shr (i-1)  and 1);
end;

procedure init;
var     i,j,k:longint;
        ac:boolean;
begin
        for i:=0 to maxV do
        for j:=1 to 8 do
        bit[i,j]:=getbit(i,9-j);

        for i:=0 to maxV do
        begin
                ac:=true;
                for j:=1 to 7 do
                if (bit[i,j]=1) and (bit[i,j+1]=1) then
                begin
                        ac:=false;
                        break;
                end;
                if ac then
                begin
                        inc(d);
                        cfg[d]:=i;
                end;
        end;

        for i:=1 to d do
        for j:=1 to d do
        begin
                ac:=true;
                for k:=1 to 8 do
                if (bit[cfg[i],k]=1) and (bit[cfg[j],k]=1) then
                begin
                        ac:=false;
                        break;
                end;
                if ac then
                begin
                        inc(len[i]);
                        s[i,len[i]]:=j;
                end;
        end;

        for i:=1 to n do
        for j:=1 to d do
        begin
                sum[i,j]:=0;
                for k:=1 to 8 do
                if bit[cfg[j],k]=1 then
                sum[i,j]:=sum[i,j]+a[i,k];
        end;

        for j:=1 to d do
        f[1,j]:=sum[1,j];

end;

procedure dp;
var     i,j,k:longint;
begin

        for i:=2 to n do
        for j:=1 to d do
        begin
                for k:=1 to len[j] do
                f[i,j]:=max(f[i,j],f[i-1,s[j,k]]);
                f[i,j]:=f[i,j]+sum[i,j];
        end;
end;

procedure output;
var     i,j:longint;
        res:int64;
begin
        res:=low(int64);
        for i:=1 to d do
        res:=max(res,f[n,i]);
        if res=0 then
        begin
                res:=low(int64);
                for i:=1 to n do
                for j:=1 to 8 do
                res:=max(res,a[i,j]);
        end;
        write(res);
end;



begin
        input;
        init;
        dp;
        output;
end.

Download