Submission #1247104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247104		kaiboy	Vim (BOI13_vim)	C++20	50 / 100	7 ms	1352 KiB

vim

#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 500;
const int   A = 10;
const int INF = 0x3f3f3f3f;

char aa[N + 1];
int qq[N][A], dp[N][N], dd[N], qu[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> aa;
	for (int i = n - 1; i >= 0; i--) {
		aa[i] -= 'a';
		if (i + 1 < n) {
			for (int a = 0; a < A; a++)
				qq[i][a] = qq[i + 1][a];
			qq[i][(int) aa[i + 1]] = i + 1;
		} else
			for (int a = 0; a < A; a++)
				qq[i][a] = n;
	}
	for (int i = 0; i < n; i++)
		for (int j = i; j < n; j++)
			dp[i][j] = INF;
	dp[0][0] = 0;
	for (int i = 0; i < n; i++) {
		int i_ = n;
		if (aa[i] != 4)
			i_ = i;
		else
			for (int a = 0; a < A; a++)
				if (a != 4)
					i_ = min(i_, qq[i][a]);
		for (int j = i_; j < n; j++)
			dd[j] = INF;
		dd[i_] = 0;
		for (int j = i_; j < n; j++) {
			int d = dd[j] + 1;
			for (int a = 0; a < A; a++)
				if (a != 4) {
					int k = qq[j][a];
					if (k < n)
						dd[k] = min(dd[k], d);
				}
		}
		for (int j = i; j < n; j++) {
			int x = dp[i][j];
			if (x == INF)
				continue;
			int q = qq[j][4];
			if (q == n)
				continue;
			for (int k = max(q, i_); k < n; k++)
				if (dd[k] != INF)
					dp[q][k] = min(dp[q][k], x + dd[k] * 2 + k - q);
		}
	}
	int ans = INF;
	for (int j = n - 1; j >= 0; j--) {
		for (int i = 0; i <= j; i++)
			ans = min(ans, dp[i][j]);
		if (aa[j] == 4)
			break;
	}
	for (int i = 0; i < n; i++)
		if (aa[i] == 4)
			ans++;
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40