IOI '07 P4 - Miners

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int countUnique(int a, int b, int c) {
    if (a==3) a=c;
    if (b==3) b=c;
    if (a==b && b==c) return 1;
    if (a==b || b==c || a==c) return 2;
    return 3;
}

int main() {
    int n; string s;
    cin >> n >> s;
    for (char &c : s) {
        if (c == 'M') c = '0';
        else if (c == 'F') c = '1';
        else c = '2';
    }

    int dp[4][4][4][4]{}; // prev1, prevprev1, prev2, prevprev2
    // 3 means no set value (not enough in group)
    fill_n(dp[0][0][0], sizeof(dp)/sizeof(dp[0][0][0][0]), -INF);
    dp[3][3][3][3] = 0;

    for (int i = 1; i <= n; ++i) {
        int dp2[4][4][4][4]{};
        fill_n(dp2[0][0][0], sizeof(dp2)/sizeof(dp2[0][0][0][0]), -INF);

        int nxt = s[i-1]-'0';
        for (int p1 = 0; p1 <= 3; ++p1) {
            for (int pp1 = 0; pp1 <= 3; ++pp1) {
                for (int p2 = 0; p2 <= 3; ++p2) {
                    for (int pp2 = 0; pp2 <= 3; ++pp2) {
                        // next -> 1
                        dp2[p1][nxt][pp2][p2] = max(dp2[p1][nxt][pp2][p2], dp[pp1][p1][pp2][p2] + countUnique(pp1, p1, nxt));

                        // next -> 2
                        dp2[pp1][p1][p2][nxt] = max(dp2[pp1][p1][p2][nxt], dp[pp1][p1][pp2][p2] + countUnique(pp2, p2, nxt));
                    }
                }
            }
        }
        copy(begin(dp2[0][0][0]), end(dp2[3][3][3]), begin(dp[0][0][0]));
    }
    cout << *max_element(begin(dp[0][0][0]), end(dp[3][3][3])) << endl;
    return 0;
}