Entrenamiento IOI - Etapa #2 - Problem: IOI07 Miners - Judge: SPOJ - 24/01/2015 - Puntaje: 100% (AC) - DP (Dynamic Programming) & Mathematics.

gistfile1.cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAXN 100005
#define REP(i,x,y)\
        for(i=((int) x); i<=((int) y); ++i){
#define END }
using namespace std;
int N;
char FOOD[MAXN];
int F[MAXN];
void leer(){
    int i;
    scanf("%s",FOOD);
    for(i=0; i<N; ++i){
        if(FOOD[i]=='M'){
            F[i+1]=1;
        }
        else if(FOOD[i]=='B'){
            F[i+1]=2;
        } else {
            F[i+1]=3;
        }
    }
}
int diferentes(int A, int B, int C) {
  int dif = 0;
  if ( A == 1 || B == 1 || C == 1 ){
    ++dif;
  }
  if ( A == 2 || B == 2 || C == 2 ){
    ++dif;
  }
  if ( A == 3 || B == 3 || C == 3 ){
    ++dif;
  }
  return dif;
}
int DP[2][4][4][4];
int ans(){
    int M[2]={0};
    int i,j,k;
    int idx;
    int tiempo = 1;
    for( idx=N; idx>=1; --idx ){
        REP(i,0,3)
            REP(j,0,3)
                REP(k,0,3)
                    M[0] = diferentes(F[idx], F[idx-1], i) + DP[tiempo][F[idx-1]][j][k];
                    M[1] = diferentes(F[idx], j, k) + DP[tiempo][j][F[idx-1]][i];
                    DP[!tiempo][i][j][k] = max(M[0], M[1]);
                END
            END
        END
        tiempo = !tiempo;
    }
    return DP[tiempo][0][0][0];
}
int main(){
    scanf("%d",&N);
    leer();
    printf("%d\n", ans());
    return 0;
}