比赛 2026.8.28 评测结果 AAAAAAAAAA
题目名称 终将成为你 最终得分 100
用户昵称 赵飞羽 运行时间 0.935 s
代码语言 C++ 内存使用 132.27 MiB
提交时间 2026-08-28 09:20:28
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int N = 70010, S = 15;
int n, m, cnt, flag = 1, a[N], f[N][S], g[N][S][S], s[N];
string str;

int dp() {
	for (int i = 1; i <= n; i++) {
		for (int x = 1; x < S; x++) {
			if (!a[i] && s[i] != x) f[i][x] = min(f[i-1][x], f[i][x]);
			f[i][x] = min(f[i-1][s[i]] + 2, f[i][x]);
		}
		for (int x = 1; x < S; x++) {
			if (s[i] != x) f[i][x] = min(g[i-1][s[i]][x], f[i][x]);
			f[i][x] = min(g[i-1][s[i]][s[i]] + 2, f[i][x]);
		}
		for (int x = 1; x < S; x++) {
			for (int y = 1; y < S; y++) {
				if (s[i] != x) g[i][x][y] = min(f[i-1][x] + 3, g[i][x][y]);
				g[i][x][y] = min(f[i-1][s[i]] + 5, g[i][x][y]);
			}
		}
		for (int x = 1; x < S; x++) {
			for (int y = 1; y < S; y++) {
				if (s[i] != x && s[i] != y) g[i][x][y] = min(g[i-1][x][y] + 1, g[i][x][y]);
				if (s[i] != y) g[i][x][y] = min(g[i-1][s[i]][y] + 3, g[i][x][y]);
				if (s[i] != x) g[i][x][y] = min(g[i-1][x][s[i]] + 3, g[i][x][y]);
				g[i][x][y] = min(g[i-1][s[i]][s[i]] + 5, g[i][x][y]);
			}
		}
	}
	return f[n][14];
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("become.in", "r", stdin);
	freopen("become.out", "w", stdout);
	cin >> n >> str;
	for (int i = 1; i <= n; i++) {
		if (str[i-1] == 'e') cnt++, flag = 1;
		else {
			s[++m] = str[i-1] - 'a' + 1;
			a[m] = flag;
			flag = 0;
		}
	}
	n = m;
	s[n+1] = 14;
	memset(f, 0x3f, sizeof(f));
	memset(g, 0x3f, sizeof(g));
	f[0][s[1]] = 0;
	cout << dp() + cnt * 2 - 2;
	return 0;
}