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=105;
      r:array[0..7] of longint=(0,1,1,2,1,2,2,3);
      p:array[1..3] of longint=(1,2,4);
var n,re,res:longint;
    a:array[1..maxn] of byte;
    g:array[1..maxn,0..7,0..7] of longint;
    f:array[1..maxn,0..7,0..7,0..3*maxn] of longint;
    d,e:array[0..7,0..7] of byte;

function out(x,y:longint):boolean;
begin
     out:=(y<>(x or y));
end;

procedure rf;
var i,j:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     for i:=1 to n do readln(a[i]);
     fillchar(d,sizeof(d),0);
     for i:=0 to 7 do
         for j:=0 to 7 do
         begin
              if not(out(1,i) or out(4,j)) then
              begin
                   d[i,j]:=1;
                   d[j,i]:=1;
              end;
              if not(out(4,i) or out(1,j)) then
              begin
                   d[i,j]:=1;
                   d[j,i]:=1;
              end;
              if not(out(1,i) or out(2,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
              if not(out(2,i) or out(1,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
              if not(out(2,i) or out(4,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
              if not(out(4,i) or out(2,j)) then
              begin
                   e[i,j]:=1;
                   e[j,i]:=1;
              end;
         end;
     close(input);
end;

function check(i,j:longint):boolean;
begin
     check:=(a[i]=0) or out(p[a[i]],j);
end;

procedure pr;
var i,j,k,l,t,lt:longint;
begin
     fillchar(f,sizeof(f),0);
     fillchar(g,sizeof(g),0);
     for i:=0 to 7 do
     begin
          if check(1,i) then
          begin
               g[1,i,0]:=r[i]; f[1,i,0,r[i]]:=1;
          end;
     end;
     for i:=2 to n do
     begin
          for j:=0 to 7 do
              for k:=0 to 7 do
                  for l:=0 to 7 do
                      if (d[j,k]=0) and check(i,j) then
                         if (i=2) or (e[j,l]=0) then
                         begin
                              lt:=g[i-1,k,l];
                              t:=lt+r[j];
                              if g[i,j,k]<t then
                                 g[i,j,k]:=t;
                              f[i,j,k,t]:=f[i,j,k,t]+f[i-1,k,l,lt];
                         end;
     end;
     re:=0; res:=0;
     for i:=0 to 7 do
         for j:=0 to 7 do
             if g[n,i,j]>res then res:=g[n,i,j];
     for i:=0 to 7 do
         for j:=0 to 7 do
             re:=re+f[n,i,j,res];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(res,' ',re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 110;
const int gain[] = {0, 1, 1, 2, 1, 2, 2, 3};
const int mask1[] = {0, 4, 0, 4, 1, 5, 1, 5};
const int mask2[] = {0, 2, 5, 7, 2, 2, 7, 7};
using namespace std;
int Z[N], F[N][8][8], C[N][8][8];
int n;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", Z + i), Z[i]--, Z[i] = Z[i] < 0 ? 0 : (1 << Z[i]);
    F[1][Z[1]][Z[2]] = 0; C[1][Z[1]][Z[2]] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < 8; j++)
        if (Z[i] == 0 || (j & Z[i]))
            for(int k = 0; k < 8; k++)
            if (Z[i + 1] == 0 || (k & Z[i + 1])) {
                if (C[i][j][k] == 0) continue;
                int &now = F[i][j][k];
                for(int p = 0; p < 8; p++)
                if ((p & j) == 0) {
                    int t1 = k | mask1[p], t2 = Z[i + 2] | mask2[p];
                    int &next = F[i + 1][t1][t2];
                    if (next < now + gain[p]) {
                        next = now + gain[p];
                        C[i + 1][t1][t2] = C[i][j][k];
                    } else
                    if (next == now + gain[p])
                        C[i + 1][t1][t2] += C[i][j][k];
                }
            }
    int res = 0, cnt = 0;
    for(int i = 0; i < 8; i++) for(int j = 0; j < 8; j++)
    if (res < F[n + 1][i][j]) {
        res = F[n + 1][i][j];
        cnt = C[n + 1][i][j];
    }
    else
    if (res == F[n + 1][i][j])
        cnt += C[n + 1][i][j];
    printf("%d %d", res, cnt);
    return 0;
}

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=1111;
  cal:array[0..7] of longint=(0,1,1,2,1,2,2,3);
var
  n:longint;
  d,count:array[1..MAXN,0..7,0..7] of longint;
  f1,f2:text;
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,u,j:longint;
begin
  read(f1,n);
  read(f1,u);
  if n=1 then
    begin
      if u=0 then writeln('3 1')
      else writeln('2 1');
      halt;
    end;
  case u of
    1: for j:=0 to 7 do
         begin
           d[2,1,j]:=-1;
           d[2,3,j]:=-1;
           d[2,5,j]:=-1;
           d[2,7,j]:=-1;
         end;
    2: for j:=0 to 7 do
         begin
           d[2,2,j]:=-1;
           d[2,3,j]:=-1;
           d[2,6,j]:=-1;
           d[2,7,j]:=-1;
         end;
    3: for j:=0 to 7 do
         begin
           d[2,4,j]:=-1;
           d[2,5,j]:=-1;
           d[2,6,j]:=-1;
           d[2,7,j]:=-1;
         end;
  end;
  for i:=2 to n do
    begin
      read(f1,u);
      case u of
        1: begin
             for j:=0 to 7 do
               begin
                 d[i+1,1,j]:=-1;
                 d[i+1,3,j]:=-1;
                 d[i+1,5,j]:=-1;
                 d[i+1,7,j]:=-1;
               end;
             for j:=0 to 7 do
               begin
                 d[i,j,1]:=-1;
                 d[i,j,3]:=-1;
                 d[i,j,5]:=-1;
                 d[i,j,7]:=-1;
               end;
           end;
        2: begin
             for j:=0 to 7 do
               begin
                 d[i+1,2,j]:=-1;
                 d[i+1,3,j]:=-1;
                 d[i+1,6,j]:=-1;
                 d[i+1,7,j]:=-1;
               end;
             for j:=0 to 7 do
               begin
                 d[i,j,2]:=-1;
                 d[i,j,3]:=-1;
                 d[i,j,6]:=-1;
                 d[i,j,7]:=-1;
               end;
           end;
        3: begin
             for j:=0 to 7 do
               begin
                 d[i+1,4,j]:=-1;
                 d[i+1,5,j]:=-1;
                 d[i+1,6,j]:=-1;
                 d[i+1,7,j]:=-1;
               end;
             for j:=0 to 7 do
               begin
                 d[i,j,4]:=-1;
                 d[i,j,5]:=-1;
                 d[i,j,6]:=-1;
                 d[i,j,7]:=-1;
               end;
           end;
      end;
    end;
end;
procedure ans;
var
  kq,sl,i1,i2:longint;
begin
  kq:=0;
  for i1:=0 to 7 do
  for i2:=0 to 7 do
    if d[n,i1,i2]>kq then kq:=d[n,i1,i2];
  write(f2,kq); sl:=0;
  for i1:=0 to 7 do
  for i2:=0 to 7 do
    if d[n,i1,i2]=kq then inc(sl,count[n,i1,i2]);
  writeln(f2,' ',sl);
end;
function check1(u,v:longint):boolean;
begin
  if (u mod 2=1) and (v>=4) then exit(false);
  if (u>=4) and (v mod 2=1) then exit(false);
  exit(true);
end;
function check2(u,v:longint):boolean;
begin
  if (u mod 2=1) and (v=2) then exit(false);
  if (u mod 2=1) and (v=3) then exit(false);
  if (u mod 2=1) and (v=6) then exit(false);
  if (u mod 2=1) and (v=7) then exit(false);
  if (u>=4) and (v=2) then exit(false);
  if (u>=4) and (v=3) then exit(false);
  if (u>=4) and (v=6) then exit(false);
  if (u>=4) and (v=7) then exit(false);
  if (v mod 2=1) and (u=2) then exit(false);
  if (v mod 2=1) and (u=3) then exit(false);
  if (v mod 2=1) and (u=6) then exit(false);
  if (v mod 2=1) and (u=7) then exit(false);
  if (v>=4) and (u=2) then exit(false);
  if (v>=4) and (u=3) then exit(false);
  if (v>=4) and (u=6) then exit(false);
  if (v>=4) and (u=7) then exit(false);
  exit(true);
end;
procedure solve;
var
  i1,i2,i3,i:longint;
begin
  for i1:=0 to 7 do
  for i2:=0 to 7 do
    if check1(i1,i2)=false then
        for i:=2 to n do
          d[i,i1,i2]:=-1;
  for i1:=0 to 7 do
  for i2:=0 to 7 do
  if d[2,i1,i2]=0 then
    begin
      d[2,i1,i2]:=cal[i1]+cal[i2];
      count[2,i1,i2]:=1;
    end;
  for i:=2 to n-1 do
  for i1:=0 to 7 do
  for i2:=0 to 7 do
    if d[i,i1,i2]>0 then
      for i3:=0 to 7 do
      if d[i+1,i2,i3]>=0 then
        if check2(i1,i3) and check1(i2,i3) then
          if d[i,i1,i2]+cal[i3]>d[i+1,i2,i3] then
            begin
              d[i+1,i2,i3]:=d[i,i1,i2]+cal[i3];
              count[i+1,i2,i3]:=count[i,i1,i2];
            end
          else if d[i,i1,i2]+cal[i3]=d[i+1,i2,i3] then
            begin
              d[i+1,i2,i3]:=d[i,i1,i2]+cal[i3];
              inc(count[i+1,i2,i3],count[i,i1,i2]);
            end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 111
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int f[70][maxn],C[70][maxn],n,a[maxn],the,A,B,so,m,r0[5],r1[5],r2[5],KQ=0,KQ1 = 0;

int main(){
    // freopen("VKNIGHTS.in","r",stdin);
     scanf("%d",&n);
     for(int i = 1;i<=n;i++)  scanf("%d",&a[i]);
     if(n==1){
           printf("%d 1",3-(a[1]!=0));
           return 0;
     }
     memset(f,0,sizeof(f));
     memset(C,0,sizeof(C));
     for(int i = 0;i<8;i++){
           the = i;
           so = 0;
           for(int t= 1;t<=3;t++){
                r0[t] = the%2;
                the/=2;
                so+=r0[t];
           }
           if(!r0[a[1]]){
                 f[i][0] = so;
                 C[i][0] = 1;
           }
          // printf("%d\n",f[i][0]); 
     }
     for(int i = 1;i<n;i++){
           for(int j = 0;j<1<<6;j++){

                A = j/8; m = A; 
                B = j%8;
                so = 0;
                //printf("%d %d %d %d\n",i,j,A,B);  
                for(int t = 1;t<=3;t++){
                     r1[t] = A%2;
                     r2[t] = B%2;
                     A/=2;
                     B/=2;
                     if(r2[t]) so++;
                }
                if(r1[a[i]] || r2[a[i+1]] || (r1[1]&&r2[3])||(r1[3]&&r2[1]))
                      continue;
                for(int k = 0;k<8;k++){
                      the = k;
                      for(int t= 1;t<=3;t++){
                           r0[t] = the%2;
                           the/=2;
                      }
                      if((r0[1]&&r1[3])||(r0[3]&&r1[1])||(r0[1]&&r2[2])||(r0[3]&&r2[2])||(r0[2]&&r2[1])||(r0[2]&&r2[3]))
                            continue;
                      if(f[j][i] < f[k*8+m][i-1]+so){
                            f[j][i] = f[k*8+m][i-1]+so;
                            C[j][i] = C[k*8+m][i-1];
                      }
                      else if(f[j][i] == f[k*8+m][i-1]+so) C[j][i] += C[k*8+m][i-1];
                }
                if(i==n-1){
                     if(KQ <= f[j][i]){
                           if(KQ<f[j][i])   KQ1 = C[j][i];
                           else KQ1 += C[j][i];
                           KQ = f[j][i];                   
                     }
                }     

                //printf("%d %d",i,j,f[i][j]);          
           }
     }
     printf("%d %d",KQ,KQ1);
    // getch();
}

Code mẫu của khuc_tuan

import java.util.*;
import java.math.*;

public class Main {

    static int[][] hs = {{4,2},{3,5},{4,0}};

    static boolean check(int b, int nb) {
        for(int i=0;i<3;++i) if((nb&(1<<i))!=0) {
            for(int t=0;t<2;++t) if((b&(1<<(hs[i][t])))!=0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] Z = new int[n];
        for(int i=0;i<n;++i) Z[i] = sc.nextInt();
        long[][][] F = new long[n+1][151][1<<6];
        F[0][0][0] = 1;
        for(int i=0;i<n;++i) for(int b=0;b<(1<<6);++b) for(int sm=0;sm<F[i].length;++sm) if(F[i][sm][b]>0) {
            for(int nb=0;nb<(1<<3);++nb) if(check(b, nb)) {
                int dem = 0;
                boolean ok = true;
                for(int j=0;j<3;++j) if((nb&(1<<j))!=0) {
                    ++dem;
                    if(j+1==Z[i]) ok = false;
                }
                if(ok) {
                    F[i+1][sm+dem][((b&7)<<3)|nb] += (F[i][sm][b]);
                }
            }
        }
        for(int sm=F[n].length-1;sm>=0;--sm) {
            long total = 0;
            for(int b=0;b<(1<<6);++b) total += (F[n][sm][b]);
            if(total>0) {
                System.out.println(sm+" " +total);
                break;
            }
        }
    }
}