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.