Hiitdromes

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

const int N = 1111;


int dp[N][N];

const int inf = 1e9;

bool is_hiit(char c) {
	if (c == 'H') return 1;
	if (c == 'I') return 1;
	if (c == 'I') return 1;
	if (c == 'T') return 1;
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	string s;
	cin >> s;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			dp[i][j] = inf;

	dp[0][0] = 0;
	
	auto offer = [&](int &state, int c) {
		state = min(state, c);
	};

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n && i + j <= n; ++j) {
			offer(dp[i + 1][j], dp[i][j] + 1);
			offer(dp[i][j + 1], dp[i][j] + 1);
			if (is_hiit(s[i])) {
				offer(dp[i + 1][j + 1], dp[i][j] + 1);
			}
			if (is_hiit(s[n - j - 1])) {
				offer(dp[i + 1][j + 1], dp[i][j] + 1);
			}
			if (is_hiit(s[i]) && s[i] == s[n - j - 1]) {
				offer(dp[i + 1][j + 1], dp[i][j]);
			}
		}
	}

	int ans = inf;

	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (i + j >= n) {
				ans = min(ans, dp[i][j]);
			}
		}
	}

	cout << ans << 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