Hiitdromes

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX_N = 1e3 + 23;
const int INF   = 1e9;

int dp[MAX_N][MAX_N];
string s;

bool check_symbol(char c)
{
    return (c == 'H') || (c == 'I') || (c == 'T');
}

int calc_dp(int l, int r)
{
    if (dp[l][r] != INF)
        return dp[l][r];

    if (l > r)
    {
        dp[l][r] = INF;
        assert(false);
        return dp[l][r];
    }

    if (l == r)
    {
        dp[l][r] = (!check_symbol(s[l]));
        return dp[l][r];
    }

    if ((l + 1) == r)
    {
        if ((!check_symbol(s[l])) && (!check_symbol(s[r])))
            dp[l][r] = 2;
        else if (s[l] == s[r])
            dp[l][r] = 0;
        else
            dp[l][r] = 1;
        return dp[l][r];
    }

    dp[l][r] = INF;

    // Add a new symbol after s[r] that equals to s[l]
    if (l + 1 <= r)
    {
        int extra = 0;
        if (!check_symbol(s[l]))
            extra = 2;
        else
            extra = 1;
        dp[l][r] = min(dp[l][r], calc_dp(l + 1, r) + extra);
    }

    // Delete symbol s[r]
    if (l <= r - 1)
        dp[l][r] = min(dp[l][r], calc_dp(l, r - 1) + 1);

    // Replace symbol s[r] by symbol that equals to s[l]
    if ((l + 1) <= (r - 1))
    {
        int extra = 0;
        if ((!check_symbol(s[l])) && (!check_symbol(s[r])))
            extra = 2;
        else if (s[l] == s[r])
            extra = 0;
        else
            extra = 1;
        dp[l][r] = min(dp[l][r], calc_dp(l + 1, r - 1) + extra);
    }

    assert(dp[l][r] != INF);

    return dp[l][r];
}

int main()
{
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    cin >> s;

    for (int i = 0; i < MAX_N; i++)
        for (int j = 0; j < MAX_N; j++)
            dp[i][j] = INF;

    int answer = calc_dp(0, n - 1);
    cout << answer << '\n';

    return 0;
}

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: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED