Hướng dẫn giải của VOI 06 Bài 1 - Chọ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
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; }
Bình luận