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.

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

Please read the guidelines before commenting.


There are no comments at the moment.