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 fi='';
      oo=1000000000;
var f:array[0..1,0..3,0..3,0..3,0..3] of longint;
    g:array[0..3,0..3,0..3] of longint;
    h:array[1..10,0..1] of longint;
    e:array[0..3] of longint;
    n,i,z,re,a,b,c,d,x,p,q:longint;
    ch:char;

procedure rset(z:longint);
var a,b,c,d:longint;
begin
     for a:=0 to 3 do
         for b:=0 to 3 do
           for c:=0 to 3 do
             for d:=0 to 3 do
                 f[z,a,b,c,d]:=-oo;
     c:=0;
     for a:=1 to 3 do
       for b:=1 to 3 do
       begin
            inc(c);
            h[c,0]:=a;
            h[c,1]:=b;
       end;
     h[10,0]:=0; h[10,1]:=0;
end;

function calc(a,b,c:longint):longint;
var i,r:longint;
begin
     r:=0;
     for i:=1 to 3 do e[i]:=0;
     inc(e[a]); inc(e[b]); inc(e[c]);
     for i:=1 to 3 do
         if e[i]>0 then inc(r);
     calc:=r;
end;

begin
     assign(input,fi); reset(input);
     readln(n);
     rset(0); rset(1);
     f[0,0,0,0,0]:=0;
     for a:=0 to 3 do
         for b:=0 to 3 do
             for c:=0 to 3 do
                 g[a,b,c]:=calc(a,b,c);
     for i:=1 to n do
     begin
          z:=i and 1;
          read(ch);
          case ch of
            'M':x:=1;
            'F':x:=2;
            else x:=3;
          end;
          for p:=1 to 10 do
           for q:=1 to 10 do
            if (p<>10) or (q<>10) or (i=1) then
            begin
                 a:=h[p,0]; b:=h[p,1];
                 c:=h[q,0]; d:=h[q,1];
                 if p+q=20 then
                 begin
                      f[z,0,0,x,x]:=1;
                      f[z,x,x,0,0]:=1;
                 end
                 else
                 begin
                      if p=10 then
                      begin
                           f[z,x,x,c,d]:=max(f[z,x,x,c,d],f[1-z,0,0,c,d]+1);
                           f[z,0,0,d,x]:=max(f[z,0,0,d,x],f[1-z,0,0,c,d]+g[c,d,x]);
                      end
                      else
                      begin
                           if q=10 then
                           begin
                                f[z,a,b,x,x]:=max(f[z,a,b,x,x],f[1-z,a,b,0,0]+1);
                                f[z,b,x,0,0]:=max(f[z,b,x,0,0],f[1-z,a,b,0,0]+g[a,b,x]);
                           end
                           else
                           begin
                                f[z,b,x,c,d]:=max(f[z,b,x,c,d],f[1-z,a,b,c,d]+g[a,b,x]);
                                f[z,a,b,d,x]:=max(f[z,a,b,d,x],f[1-z,a,b,c,d]+g[c,d,x]);
                           end;
                      end;
                 end;
            end;
     end;
     re:=n;
     for a:=0 to 3 do
       for b:=0 to 3 do
         for c:=0 to 3 do
           for d:=0 to 3 do
             re:=max(re,f[z,a,b,c,d]);
     writeln(re);
     close(input);
end.

Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100000;
int f[N + 1][4][4][4][4];

int numDistinct(int x, int y, int z) {
    if(x == 3) return y == 3 || y == z ? 1 : 2;
    if(y == 3) return 1;
    if(x != y && x != z && y != z) return 3;
    if(x == y && x == z) return 1;
    return 2;
}

void checkMax(int &x, int y) {
    if(x < y) x = y;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("NKMINERS.inp", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    memset(f, 0xc1, sizeof f);
    int res = 0;
    f[0][3][3][3][3] = 0;
    for(int i = 0; i <= n; ++i) {
        int type = i == n ? -1 : s[i] == 'M' ? 0 : s[i] == 'F' ? 1 : 2;
        for(int x1 = 0; x1 < 4; ++x1) {
            for(int y1 = 0; y1 < 4; ++y1) {
                for(int x2 = 0; x2 < 4; ++x2) {
                    for(int y2 = 0; y2 < 4; ++y2) {
                        if(f[i][x1][y1][x2][y2] >= 0) {
                            if(i < n) {
                                checkMax(f[i + 1][y1][type][x2][y2], f[i][x1][y1][x2][y2] + numDistinct(x1, y1, type));
                                checkMax(f[i + 1][x1][y1][y2][type], f[i][x1][y1][x2][y2] + numDistinct(x2, y2, type));
                            } else {
                                checkMax(res, f[i][x1][y1][x2][y2]);
                            }
                        }
                    }
                }
            }
        }
    }
    cout << res << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <cstdio>
const int N = 100005;
using namespace std;
int F[2][4][4][4][4];
int val[4][4][4];
int a[N];
int n, res;

void maximize(int& x, int y) {
    if (x < y) {
        x = y; if (res < x) res = x;
    }
}

int main()
{
    scanf("%d\n", &n);
    int i, j, k, x1, y1, x2, y2; char c;
    for(i=1; i<=n; i++) {
        scanf("%c", &c);
        if (c == 'M') a[i] = 1;
        if (c == 'F') a[i] = 2;
        if (c == 'B') a[i] = 3;
    }
    for(i=0; i<=3; i++) for(j=0; j<=3; j++) for(k=0; k<=3; k++) {
        if (i == 1 || j == 1 || k == 1) val[i][j][k]++;
        if (i == 2 || j == 2 || k == 2) val[i][j][k]++;
        if (i == 3 || j == 3 || k == 3) val[i][j][k]++;
    }
    int now = 0, next = 1, p, prev;
    F[now][0][a[1]][0][0] = F[now][0][0][0][a[1]] = 1;
    for(i=1; i<n; i++) {
        for(x1=0; x1<=3; x1++)
        for(y1=(x1 != 0 ? 1 : 0); y1<=3; y1++)
        for(x2=0; x2<=3; x2++)
        for(y2=(x2 != 0 ? 1 : 0); y2<=3; y2++) {
            p = a[i + 1]; prev = F[now][x1][y1][x2][y2];
            if (prev == 0) continue;
            maximize(F[next][y1][p][x2][y2], prev + val[x1][y1][p]);
            maximize(F[next][x1][y1][y2][p], prev + val[x2][y2][p]);
        }
        next ^= 1; now ^= 1;
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define MAXN 100111
using namespace std;

int n,a[MAXN],f[2][4][4][4][4],cnt[4][4][4];
char s[MAXN];

void inp() {
    scanf("%d\n",&n);
    gets(s);
    FOR(i,1,n)
        if (s[i-1]=='M') a[i]=0;
        else if (s[i-1]=='F') a[i]=1;
        else a[i]=2;
}

void solve() {
    FOR(x,0,3)
    FOR(y,0,3)
    FOR(z,0,3)
        FOR(t,0,2)
            if (x==t || y==t || z==t) cnt[x][y][z]++;

    memset(f,-1,sizeof f);
    f[0][3][3][3][3]=0;
    int now=0;
    FOR(i,0,n-1) {
        int u=a[i+1];
        now=1-now;
        FOR(a1,0,3)
        FOR(a2,0,3)
        FOR(b1,0,3)
        FOR(b2,0,3)
            if (f[1-now][a1][a2][b1][b2]>=0) {
                f[now][a2][u][b1][b2] >?= f[1-now][a1][a2][b1][b2]+cnt[a1][a2][u];
                f[now][a1][a2][b2][u] >?= f[1-now][a1][a2][b1][b2]+cnt[b1][b2][u];
            }
    }

    int res=0;
    FOR(a1,0,3)
    FOR(a2,0,3)
    FOR(b1,0,3)
    FOR(b2,0,3)
        res >?= f[now][a1][a2][b1][b2];

    printf("%d\n",res);
}

int main() {
    inp();
    solve();
    return 0;
}

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 10011
#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[100111][13][13],n,A;
char s[100111];
//VVI::iterator it;

int khac (int a1,int a2,int a3){
      if(a1==0) return (a2!=a3)+1; 
      if(a1==a2 && a2==a3)
          return 1;
      if(a1==a2 && a1!=a3) return 2;
      if(a1==a3 && a1!=a2) return 2;
      if(a2==a3 && a1!=a2) return 2;
      return 3;
}

int main(){
    // freopen("NKMINERS.in","r",stdin);
      scanf("%d",&n);
      scanf("%s",s);
      memset(f,-1,sizeof(f));
      f[0][0][0] = 0;
      for(int ii = 1 ;ii<=n;ii++){
            if(s[ii-1]=='M') A = 1;
            if(s[ii-1]=='B') A = 2;
            if(s[ii-1]=='F') A = 3;
            for(int i = 0;i<13;i++){
                 for(int j = 0;j<=3;j++){
                      if(j==0){
                            if(f[ii-1][0][i]!=-1) f[ii][A][i] = f[ii-1][0][i]+1;
                            if(f[ii-1][i][0]!=-1) f[ii][i][A] = f[ii-1][i][0]+1;
                      }
                      else{
                            for(int k = 0;k<=3;k++){
                                 if(f[ii-1][k*3+j][i]!=-1)  f[ii][j*3+A][i] >?= f[ii-1][k*3+j][i]+khac(k,j,A);
                                 if(f[ii-1][i][k*3+j]!=-1)  f[ii][i][j*3+A] >?= f[ii-1][i][k*3+j]+khac(k,j,A);
                            }
                      }
                 }
            }    
      }
      int KQ = 0;
      for(int i = 0;i<13;i++)
           for(int j = 0;j<13;j++)
               KQ >?= f[n][i][j];
      printf("%d",KQ);
     // getch();
}

Code mẫu của ll931110

{$MODE DELPHI,R+,Q+,H+}
program NKMINERS;
const
  input  = '';
  output = '';
  maxv = 100000 * 100;
  maxk = 9;
  link: array[0..9,1..3] of integer = ((1,2,3),(1,4,5),(6,2,7),(8,9,3),
                                       (6,2,7),(8,9,3),(1,4,5),(8,9,3),
                                       (1,4,5),(6,2,7));
  cost: array[0..9,1..3] of integer = ((1,1,1),(1,2,2),(2,1,2),(2,2,1),
                                       (2,2,3),(2,3,2),(2,2,3),(3,2,2),
                                       (2,3,2),(3,2,2));
  //state: 0[0],1[1],2[2],3[3],12[4],13[5],21[6],23[7],31[8],32[9]
var
  cur,next: array[0..maxk,0..maxk] of integer;
  n,res: integer;
  s: string;

procedure init;
var
  f: text;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  readln(f, s);

  close(f);
end;

procedure solve;
var
  i,j,t,ek,ds,dc: integer;
  ch: char;
begin
  for i := 0  to maxk do
    for j := 0 to maxk do cur[i,j] := -maxv;
  cur[0,0] := 0;
  next := cur;

  for t := 1 to n do
    begin
      ch := s[t];
      case ch of
        'M': ek := 1;
        'F': ek := 2;
        'B': ek := 3;
      end;

      for i := 0 to maxk do
        for j := 0 to maxk do
          begin
            ds := link[i,ek];
            dc := cost[i,ek];
            if next[ds,j] < cur[i,j] + dc then next[ds,j] := cur[i,j] + dc;

            ds := link[j,ek];
            dc := cost[j,ek];
            if next[i,ds] < cur[i,j] + dc then next[i,ds] := cur[i,j] + dc;
          end;

      cur := next;
    end;

  res := 0;
  for i := 0 to maxk do
    for j := 0 to maxk do
      if res < cur[i,j] then res := cur[i,j];
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define maximize(x,y) if (x<(y)) x=(y)
#define ok
int n;
char s[MAX];
int f[MAX][4][4][4][4];
inline int count(int x,int y,int z) {
    bool ex[7];
    memset(ex,false,sizeof ex);
    ex[x]=true;
    ex[y]=true;
    ex[z]=true;
    int ret=0;
    FOR(i,1,3) if (ex[i]) ret++;
    return (ret);
}
void init(void) {
    scanf("%d",&n);
    scanf("%s",s+1);
    FOR(i,1,n) {
        if (s[i]=='M') s[i]=1;
        if (s[i]=='F') s[i]=2;
        if (s[i]=='B') s[i]=3;
    }
}
void optimize(void) {
    f[1][0][s[1]][0][0]=1;
    f[1][0][0][0][s[1]]=1;  
    FOR(i,1,n-1) REP(p11,4) REP(p12,4) REP(p21,4) REP(p22,4)
        if (f[i][p11][p12][p21][p22]>0) {
            maximize(f[i+1][p12][s[i+1]][p21][p22],f[i][p11][p12][p21][p22]+count(p11,p12,s[i+1]));
            maximize(f[i+1][p11][p12][p22][s[i+1]],f[i][p11][p12][p21][p22]+count(p21,p22,s[i+1]));
        }
    int res=0;
    FOR(p11,1,3) REP(p11,4) REP(p12,4) REP(p21,4) REP(p22,4)
        maximize(res,f[n][p11][p12][p21][p22]);
    printf("%d",res);
}
int main(void) {
    init();
    optimize();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>

using namespace std;

int n;
char a[100010];
int f[4][4][4][4], g[4][4][4][4];

int main() {

    scanf("%d", &n);
    gets(a);
    gets(a);

    memset( f, -1, sizeof(f));
    f[3][3][3][3] = 0;

    for(int i=0;i<n;++i) {
        memset( g, -1, sizeof(g));
        int next = 0;
        if(a[i]=='M') next = 1;
        if(a[i]=='F') next = 2;
        for(int i00=0;i00<4;++i00) for(int i01=0;i01<4;++i01) {
            for(int i10=0;i10<4;++i10) for(int i11=0;i11<4;++i11) if(f[i00][i01][i10][i11]!=-1) {
                // cho mo 1
                int tmp = 1 + f[i00][i01][i10][i11];
                if(i01!=3 && i01!=next) ++tmp;
                if(i00!=3 && i00!=i01 && i00!=next) ++tmp;
                int &gg = g[i01][next][i10][i11];
                if(gg<tmp) gg = tmp;
                // cho mo 2
                tmp = 1 + f[i00][i01][i10][i11];
                if(i11!=3 && i11!=next) ++tmp;
                if(i10!=3 && i10!=i11 && i10!=next) ++tmp;
                int &g2 = g[i00][i01][i11][next];
                if(g2<tmp) g2 = tmp;
            }
        }
        memmove( f, g, sizeof(f));
    }
    int result = 0;
    for(int i00=0;i00<4;++i00) for(int i01=0;i01<4;++i01) 
            for(int i10=0;i10<4;++i10) for(int i11=0;i11<4;++i11) if(f[i00][i01][i10][i11]!=-1)
                result >?= f[i00][i01][i10][i11];
    cout << result << endl;
    //system("pause");
    return 0;
}