Hướng dẫn giải của Trò chơi trên ma trận


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.