PROG-2003: Miners

#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
int n;
int ar[100010];
bool check[5];
int dp[2][4][4][4][4];

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        char a;
        scanf(" %c", &a);
        if(a == 'M') ar[i] = 1;
        else if(a == 'F') ar[i] = 2;
        else ar[i] = 3;
    }

    for(int i=n;i>=1;i--){
        for(int a=0;a<=3;a++){
            for(int b=0;b<=3;b++){
                for(int c=0;c<=3;c++){
                    for(int d=0;d<=3;d++){
                        int cnt1 = 0;
                        check[a] = check[b] = check[ar[i]] = true;
                        for(int j=1;j<=3;j++) {
                            if(check[j]) cnt1 ++;
                            check[j] = false;
                        }
                        int cnt2 = 0;
                        check[c] = check[d] = check[ar[i]] = true;
                        for(int j=1;j<=3;j++){
                            if(check[j]) cnt2 ++;
                            check[j] = false;
                        }
                        dp[i%2][a][b][c][d] = max(cnt1 + dp[(i+1)%2][b][ar[i]][c][d],
                                                cnt2 + dp[(i+1)%2][a][b][d][ar[i]]);
                    }
                }
            }
        }
    }

    printf("%d", dp[1][0][0][0][0]);

    return 0;
}

/*void filled(){
    for(int j=1;j<=3;j++) check[j] = false;
}
int f(int i, int a, int b, int c, int d){
    if(i > n) return 0;
    if(dp[i][a][b][c][d] != -INF) return dp[i][a][b][c][d];
    // 1
    int cnt1 = 0;
    filled();
    check[a] = true;
    check[b] = true;
    check[ar[i]] = true;
    for(int j=1;j<=3;j++){
        if(check[j]) cnt1 ++;
    }
    // 2
    int cnt2 = 0;
    filled();
    check[c] = true;
    check[d] = true;
    check[ar[i]] = true;
    for(int j=1;j<=3;j++) {
        if(check[j]) cnt2 ++;
    }
    // recursive step
    dp[i][a][b][c][d] = max(cnt1 + f(i+1, b, ar[i], c, d), cnt2 + f(i+1, a, b, d, ar[i]));
}*/