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.
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