Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 10000
int n, a[8][N];
long long f[256][N];
int state[256], cnt;

inline long long sumCol(int col, int state) {
    long long res = 0;
    for(int i = 0; i < 8; ++i) if(state & 1 << i) res += a[i][col];
    return res;
}

void enter() {
    scanf("%d", &n);
    for(int i = 0; i < 8; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%d", &a[i][j]);
}

void solve() {
    for(int st = 0; st < 256; ++st) {
        bool ok = 1;
        for(int i = 0; i < 7 && ok; ++i) ok = (st & 3 << i) != (3 << i);
        if(ok) state[cnt++] = st;
    }
    for(int i = 0; i < cnt; ++i) f[state[i]][0] = sumCol(0, state[i]); 
    for(int i = 1; i < n; ++i)
        for(int j = 0; j < cnt; ++j) {
            long long sum = f[state[j]][i] = sumCol(i, state[j]); 
            for(int k = 0; k < cnt; ++k)
                if((state[j] & state[k]) == 0) 
                    f[state[j]][i] = max(f[state[j]][i], sum + f[state[k]][i-1]);
        }
    long long res = f[0][n-1];
    for(int i = 0; i < cnt; ++i) res = max(res, f[state[i]][n-1]);
    int mx = a[0][0]; 
    for(int i = 0; i < 8; ++i)
        for(int j = 0; j < n; ++j)
            mx = max(mx, a[i][j]);
    printf("%lld\n", mx < 0 ? mx : res);
}

int main() {
#ifdef __WATASHI
    freopen("input.txt", "r", stdin);
#endif
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

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.

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       10111;
var
  f1,f2         :       text;
  n,stt         :       longint;
  a             :       array[1..8,0..MAXN] of longint;
  tt            :       array[1..100] of longint;
  d,sum         :       array[0..MAXN,1..100] of int64;
  list          :       array[1..100,1..100] of longint;
  deg           :       array[1..100] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i,j:longint;
    begin
      read(f1,n);
      for i:=1 to 8 do
      for j:=1 to n do
        read(f1,a[i,j]);
    end;
procedure gen;
    var
      i,j,bit:longint;
    begin
      stt:=0;
      for i:=0 to 255 do
        if (i and (i>>1)=0) and (i and (i<<1)=0) then
          begin
            inc(stt);
            tt[stt]:=i;
          end;
      for i:=1 to stt do
      for j:=1 to stt do
        if tt[i] and tt[j]=0 then
          begin
            inc(deg[i]);
            list[i,deg[i]]:=j;
          end;
      for i:=1 to n do
      for j:=1 to stt do
        for bit:=1 to 8 do
          if (tt[j]>>(bit-1)) and 1=1 then
            inc(sum[i,j],a[bit,i]);
    end;
procedure solve;
    var
      i,j,now,next:longint;
      kq:int64;
    begin
      kq:=-1000111000111;
      for i:=1 to n-1 do
      for now:=1 to stt do
        d[i,now]:=kq;
      for i:=0 to n-1 do
      for now:=1 to stt do
        for j:=1 to deg[now] do
          begin
            next:=list[now,j];
            d[i+1,next]:=max(d[i+1,next],d[i,now]+sum[i+1,next]);
          end;
      for now:=1 to stt do
        kq:=max(kq,d[n,now]);
      writeln(f2,kq);
    end;
procedure refine;
    var
      i,j:longint;
      ln:int64;
    begin
      ln:=-1000111000111;
      for i:=1 to 8 do
      for j:=1 to n do
        if a[i,j]>0 then exit
        else ln:=max(ln,a[i,j]);
      writeln(f2,ln);
      closeF; halt;
    end;

begin
  openF;
  inp;
  gen;
  refine;
  solve;
  closeF;
end.

Code mẫu của ll931110

{$MODE DELPHI}
Program QBGAME;
        Const
                input  = '';
                output = '';
                  maxc = -1000000000;
        Var
                    a: array[1..8,1..10000] of longint;
                    F: array[0..55,1..10000] of int64;
                    h: array[1..56] of longint;
                  val: array[1..55] of longint;
                stack: array[1..55,1..8] of byte;
                  adj: array[1..7000] of longint;
                    n: integer;
                  max: int64;

Procedure init;
          Var
                fi: text;
               i,j: integer;
          Begin
                Assign(fi, input);
                        Reset(fi);

                        Readln(fi, n);
                        max:= low(longint);

                        For i:= 1 to 8 do
                            For j:= 1 to n do
                                        Begin
                                                Read(fi, a[i,j]);
                                                If max < a[i,j] then max:= a[i,j];
                                        End;
                Close(fi);
          End;

Procedure MakeGraph;
          Var
                count,i,j,vertex: integer;
          Begin
                vertex:= 0;
                For i:= 0 to 255 do if i and (i shl 1) = 0 then
                  Begin
                        inc(vertex);
                        val[vertex]:= i;
                        For j:= 0 to 7 do if (i and (1 shl j)) = (1 shl j)
                                then stack[vertex,j + 1]:= 1 else stack[vertex,j + 1]:= 0;
                  End;

                count:= 0;
                vertex:= 0;

                For i:= 0 to 255 do if i and (i shl 1) = 0 then
                  Begin
                        inc(vertex);
                        h[vertex]:= count;
                        For j:= 1 to 55 do if i and val[j] = 0 then
                          Begin
                                inc(count);
                                adj[count]:= j;
                          End;
                  End;

                h[vertex + 1]:= count;
          End;

Procedure optimize;
          Var
                i,j,k,s,ij: integer;
          Begin
                For i:= 1 to 55 do F[i,1]:= 0;
                For i:= 1 to 55 do
                    For k:= 1 to 8 do if stack[i,k] = 1
                                      then F[i,1]:= F[i,1] + a[k,1];

                For s:= 2 to n do
                  For i:= 1 to 55 do
                    Begin
                      F[i,s]:= maxc;
                      For ij:= h[i] + 1 to h[i + 1] do
                        Begin
                                j:= adj[ij];
                                if F[i,s] < F[j,s - 1]
                                  then F[i,s]:= F[j,s - 1];
                        End;

                      For j:= 1 to 8 do if stack[i,j] = 1
                                then F[i,s]:= F[i,s] + a[j,s];
                    End;
          End;

Procedure solve;
          Var
                    fo: text;
                     i: integer;
                   num: int64;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                        num:= 0;
                        For i:= 1 to 55 do if num < F[i,n] then num:= F[i,n];
                        If num = 0 then writeln(fo, max) else writeln(fo, num);
                Close(fo);
          End;

Begin
        init;
        MakeGraph;
        optimize;
        solve;
End.

Code mẫu của skyvn97

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n;
int a[8][10010];
long long _F[1<<8], _G[1<<8];
int inf = 1000000000;
int ds[8][100], nd[8];
int coduong = false;
int zz = -1000000000;

int main() {
    scanf("%d", &n);
    for(int i=0;i<8;++i)
        for(int j=1;j<=n;++j) {
            scanf("%d", a[i]+j);
            if(a[i][j]>=0) coduong = true;
            if(a[i][j]<0) zz = max( zz, a[i][j]);
        }

    if(!coduong) {
        cout << zz << endl;
        return 0;
    }

    for(int base=0;base<8;++base) {
        nd[base] = 0;
        for(int bit=0;bit<(1<<8);++bit) {
            bool ok = true;
            for(int i=0;i+1<8;++i) if( i!=base && (bit&(1<<i))!=0 && (bit&(1<<(i+1)))!=0 ) ok = false;
            if(ok) ds[base][nd[base]++] = bit;
        }
        //cout << nd[base] << endl;
    }
    long long *G = _G, *F = _F;
    for(int j=1;j<=n;++j) for(int i=0;i<8;++i) {
        memset( G, 0, sizeof(_G));
        for(int t=0;t<nd[i];++t) {
            int bit = ds[i][t];
            long long &r = G[bit];
            int zz = bit & (1<<i);
            int nb = bit ^ zz;
            int tmp = (zz!=0) ? a[i][j] : 0;
            r >?= F[nb] + tmp;
            nb |= 1<<i;
            if((bit&(1<<i))==0) r >?= F[nb] + tmp;
        }
        long long * tmp = G; G = F; F = tmp;
    }
    cout << *max_element(F, F+(1<<8)) << endl;
    //system("pause");
    return 0;
}