Editorial for VOI 06 Bài 1 - Chọn ô
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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
const fi=''; fo=''; maxn=10000; r:array[1..8] of longint=(0,1,2,4,5,8,9,10); p:array[0..3] of longint=(1,2,4,8); var n,re:longint; b:array[0..1,1..8] of longint; a:array[0..3,1..maxn] of longint; tr:array[1..maxn,1..8] of longint; kt:boolean; procedure rf; var i,j:longint; begin assign(input,fi); reset(input); read(n); for i:=0 to 3 do for j:=1 to n do read(a[i,j]); close(input); end; procedure pr; var i,j,k,t,q,max:longint; begin fillchar(b,sizeof(b),0); kt:=true; for i:=1 to 8 do for j:=0 to 3 do if r[i] or p[j]=r[i] then b[1,i]:=b[1,i]+a[j,1]; t:=1; for i:=2 to n do begin t:=i mod 2; for j:=1 to 8 do begin b[t,j]:=-maxlongint; for k:=1 to 8 do if r[j] and r[k] = 0 then begin max:=b[1-t,k]; for q:=0 to 3 do if r[j] or p[q] = r[j] then max:=max+a[q,i]; if max>b[t,j] then begin b[t,j]:=max; tr[i,j]:=k; end; end; end; end; re:=b[t,1]; k:=1; for i:=2 to 8 do if b[t,i]>re then begin re:=b[t,i]; k:=i; end; i:=n; if k=1 then begin while (k=1) and (i>0) do begin k:=tr[i,k]; dec(i); end; if (i=0) then kt:=false; end; end; procedure wf; var i,j:longint; begin assign(output,fo); rewrite(output); if not kt then begin re:=-maxlongint; for i:=0 to 3 do for j:=1 to n do if a[i,j]>re then re:=a[i,j]; end; write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 10005 int a[4][N], n, f[N][11]; int sts[] = {0,1,2,4,5,8,9,10}; int main() { //freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); scanf( "%d", &n ); rep(i, 4) fo(j,1,n) scanf( "%d", &a[i][j] ); fo(j,1,n) { rep(st, 8) { rep(i,4) if(sts[st] & (1<<i)) f[j][sts[st]] += a[i][j]; int mx = INT_MIN; rep(st2, 8) if((sts[st] | sts[st2])==(sts[st] ^ sts[st2])) mx = max( f[j-1][sts[st2]], mx ); f[j][sts[st]] += mx; } } int mx = INT_MIN; rep(st, 8) mx = max(f[n][sts[st]], mx); int mx2 = INT_MIN; rep(i,4) fo(j,1,n) mx2 = max(mx2, a[i][j]); printf( "%d\n", mx2 < 0 ? mx2 : mx ); return 0; }
Code mẫu của ladpro98
program qbselect; uses math; const fi=''; var com:array[0..15,0..15] of boolean; can:array[0..15] of boolean; a:array[1..10001,1..4] of longint; f,sum:array[0..10001,0..15] of longint; bit:array[0..15,1..4] of longint; n:longint; procedure input; var inp:text; var i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for j:=1 to 4 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; begin fillchar(can,sizeof(can),true); fillchar(com,sizeof(com),true); for i:=1 to n do for j:=0 to 15 do f[i,j]:=low(longint); for i:=0 to 15 do for j:=1 to 4 do bit[i,j]:=getbit(i,j); for i:=1 to n do for j:=0 to 15 do begin for k:=1 to 4 do inc(sum[i,j],bit[j,k]*a[i,k]); end; for i:=0 to 15 do begin for j:=1 to 3 do if (getbit(i,j) = 1) and (getbit(i,j+1) = 1) then can[i]:=false; end; for i:=0 to 15 do for j:=0 to 15 do begin if (not can[i]) or (not can[j]) then begin com[i,j]:=false; continue; end; for k:=1 to 4 do if (getbit(i,k) = 1) and (getbit(j,k)=1) then com[i,j]:=false; end; end; procedure dp; var i,j,k:longint; begin for i:=1 to n do begin for j:=0 to 15 do begin if not can[j] then continue; for k:=0 to 15 do if com[j,k] then f[i,j]:=max(f[i,j],f[i-1,k]+sum[i,j]); end; end; end; procedure output; var res,i,j:longint; begin res:=low(longint); for i:=0 to 15 do res:=max(res,f[n,i]); if res<>0 then write(res) else begin res:=a[1,1]; for i:=1 to n do for j:=1 to 4 do res:=max(res,a[i,j]); write(res); end; end; begin input; init; dp; output; end.
Code mẫu của RR
{$R-,Q-} uses math; const FINP=''; FOUT=''; MAXN=10000; oo=1000000000; var n:longint; a:array[1..MAXN,1..4] of longint; d:array[0..MAXN,0..15] of longint; procedure inp; var f:text; i:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do read(f,a[i,1]); for i:=1 to n do read(f,a[i,2]); for i:=1 to n do read(f,a[i,3]); for i:=1 to n do read(f,a[i,4]); close(f); end; procedure ans; var f:text; mask,kq:longint; begin assign(f,FOUT); rewrite(f); kq:=-oo; for mask:=0 to 15 do kq:=max(kq,d[n,mask]); writeln(f,kq); close(f); end; procedure refine; var i,j,kq:longint; f:text; begin for i:=1 to n do for j:=1 to 4 do if a[i,j]>0 then exit; kq:=-oo; assign(f,FOUT); rewrite(f); for i:=1 to n do for j:=1 to 4 do kq:=max(kq,a[i,j]); writeln(f,kq); close(f); halt; end; procedure solve; var mask,mask2,i,j,sum:longint; begin for i:=1 to n do for mask:=0 to 15 do if (mask and (mask shl 1)=0) and (mask and (mask shr 1)=0) then begin sum:=0; for j:=0 to 3 do if (mask shr j) and 1=1 then sum:=sum+a[i,j+1]; for mask2:=0 to 15 do if (mask2 and (mask2 shl 1)=0) and (mask2 and (mask2 shr 10)=0) then if mask and mask2=0 then d[i,mask]:=max(d[i,mask],d[i-1,mask2]+sum); end; end; begin inp; refine; solve; ans; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int main() { //freopen("QBSELECT.in","r",stdin); int f[10001][18],a[10001][6],n,max=-100000,KQ=0; scanf("%d",&n); for(int i = 1;i<=4;i++) for(int j = 1;j<=n;j++) { scanf("%d",&a[j][i]); if(max<a[j][i]) max = a[j][i]; } if(max <=0) printf("%d",max); else { for(int i = 0;i<=15;i++) f[0][i] = 0; int x[5],y[5],u,v,flag,maxx,tong; for(int i = 1;i<=n;i++) { for(int j = 0;j<=15;j++) { u=j; flag = 1; maxx = 0; tong = 0; for(int k = 1;k<=4;k++) { x[k] = u%2; u = u/2; if(k > 1 && x[k]*x[k-1]>0) { flag = 0; break; } if(x[k] == 1) tong = tong + a[i][k]; } if(flag ==0) f[i][j] = 0; else { for(int k = 0;k<=15;k++) { u = k; flag = 1; for(int l = 1;l<=4;l++) { y[l] = u%2; u = u/2; if((l > 1 && y[l]*y[l-1]>0)||(x[l]*y[l]>0)) { flag = 0; break; } } if(flag ==1 && f[i-1][k]>maxx) maxx = f[i-1][k]; } f[i][j] = tong + maxx; } } } for(int i = 0;i<=15;i++) { if(f[n][i]>KQ) KQ = f[n][i]; } printf("%d",KQ); } //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program QBSELECT; Const input = ''; output = ''; Var a: array[0..4,1..10000] of integer; F: array[0..15,1..10000] of integer; power: array[0..3] of integer; stack: array[0..15,1..4] of integer; n,max: integer; Procedure init; Var fi: text; i,j: integer; Begin Fillchar(a, sizeof(a), 0); Assign(fi, input); Reset(fi); Readln(fi, n); max:= -32000; For i:= 1 to 4 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 pwr; Var i: integer; Begin power[0]:= 1; For i:= 1 to 3 do power[i]:= power[i - 1] shl 1; End; Procedure adj; Var i,j,k: integer; Begin For i:= 0 to 15 do If i and (i shl 1) = 0 then Begin j:= 0; For k:= 0 to 3 do if (i and power[k]) = power[k] then Begin inc(j); stack[i,j]:= k + 1; End; End; End; Procedure optimize; Var i,j,k,s,tmp: integer; Begin Fillchar(F, sizeof(F), 0); For i:= 0 to 15 do For j:= 1 to 4 do F[i,1]:= F[i,1] + a[stack[i,j],1]; For k:= 2 to n do For i:= 0 to 15 do if (i and (i shl 1) = 0) then Begin F[i,k]:= low(integer); For j:= 0 to 15 do if (i and j = 0) and (j and (j shl 1) = 0) then Begin tmp:= F[j,k - 1]; If F[i,k] < tmp then F[i,k]:= tmp; End; For s:= 1 to 4 do F[i,k]:= F[i,k] + a[stack[i,s],k]; End; End; Procedure solve; Var fo: text; i,num: integer; Begin Assign(fo, output); Rewrite(fo); num:= 0; For i:= 0 to 15 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; pwr; adj; optimize; solve; End.
Code mẫu của skyvn97
#include<stdio.h> #include<vector> #define MAX 10101 using namespace std; int a[4][MAX]; int f[17][MAX]; vector<int> v[17]; int n; int res; const int INF=-2e9; void init(void) { int i,j; scanf("%d",&n); for (i=0;i<4;i=i+1) for (j=1;j<=n;j=j+1) scanf("%d",&a[i][j]); } bool fit(int s1,int s2) { int i; for (i=0;i<3;i=i+1) { if (((s1|(1<<i))==s1) && ((s1|(1<<(i+1)))==s1)) return (false); if (((s2|(1<<i))==s2) && ((s2|(1<<(i+1)))==s2)) return (false); } for (i=0;i<4;i=i+1) if (((s1|(1<<i))==s1) && ((s2|(1<<i))==s2)) return (false); return (true); } void gens(void) { int i,j; for (i=0;i<16;i=i+1) for (j=0;j<16;j=j+1) if (fit(i,j)) v[i].push_back(j); } void optimize(void) { res=INF; int i,j,k,l; for (i=0;i<4;i=i+1) for (j=1;j<=n;j=j+1) if (a[i][j]>res) res=a[i][j]; if (res<=0) { printf("%d",res); return; } for (i=0;i<16;i=i+1) for (j=1;j<=n;j=j+1) f[i][j]=INF; for (i=0;i<v[0].size();i=i+1){ f[v[0][i]][1]=0; for (j=0;j<4;j=j+1) f[v[0][i]][1]+=a[j][1]*((v[0][i]|(1<<j))==v[0][i]); } for (j=2;j<=n;j=j+1) for (i=0;i<16;i=i+1) { if (v[i].size()<1) continue; for (k=0;k<v[i].size();k=k+1) if (f[v[i][k]][j-1]>f[i][j]) f[i][j]=f[v[i][k]][j-1]; for (l=0;l<4;l=l+1) f[i][j]+=a[l][j]*((i|(1<<l))==i); } res=INF; for (i=0;i<16;i=i+1) if ((n!=1) || (i!=0)) if (res<f[i][n]) res=f[i][n]; printf("%d",res); } int main(void) { init(); gens(); optimize(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int n; int a[4][10000]; int f[1<<4], g[1<<4]; int main() { scanf("%d", &n); for(int i=0;i<4;++i) for(int j=0;j<n;++j) scanf("%d", a[i]+j); bool duong = false; int mm = -1000000000; for(int j=0;j<n;++j) for(int i=0;i<4;++i) { if(a[i][j]>0) duong = true; else mm >?= a[i][j]; memset( g, 0, sizeof(g)); for(int bit=0;bit<(1<<4);++bit) { if((bit&(1<<i))==0) { g[bit] = f[bit]; g[bit] >?= f[bit|(1<<i)]; } else { if(i==0 || (bit&(1<<(i-1)))==0) { int nb = (bit | (1<<i)) ^ (1<<i); g[bit] >?= a[i][j] + f[nb]; } } } memmove( f, g, sizeof(g)); } if(!duong) cout << mm << endl; else cout << *max_element( f, f+(1<<4)) << endl; //system("pause"); return 0; }
Comments