Hiitdromes

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define D(x) {x;}
#else
#define D(x)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int) (x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (char &c : s) {
        if (c != 'H' && c != 'I' && c != 'T') c = 'X';
    }
    int dp[n+1][n] {};
    for (int i = 0; i < n; ++i) {
        dp[0][i] = 0;
        dp[1][i] = s[i] == 'X';
    }
    // for (int i = 0; i < n-1; ++i) {
    //     int c = s[i] == 'X';
    //     c += s[i+1] == 'X';
    //     if (c == 0 && s[i] != s[i+1]) c++;
    //     dp[2][i] = c;
    // }
    for (int w = 2; w <= n; ++w) {
        for (int l = 0; l+w <= n; ++l) {
            int r = l+w-1;
            dp[w][l] = 1e9;
            {
                int c = s[l] == 'X';
                c += s[r] == 'X';
                if (c == 0 && s[l] != s[r]) c++;
                dp[w][l] = min(dp[w][l], c+dp[w-2][l+1]);
            }
            dp[w][l] = min({dp[w][l], dp[w-1][l] + 1, dp[w-1][l+1] + 1});
        }
    }
    cout << dp[n][0] << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED