제출 #208496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208496		Siberian	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1080 ms	6392 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

const int MAXN = 410;

int n;
int a[MAXN];

void read() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		char x;
		cin >> x;
		if (x == 'R') a[i] = 0;
		else if (x == 'G') a[i] = 1;
		else a[i] = 2;
	}
}

const int INF = 1e9 + 10;
int dp[MAXN][MAXN][3][3];

void build() {
	for (int l = 0; l < MAXN; l++)
		for (int r = 0; r < MAXN; r++)
			for (int chL = 0; chL < 3; chL++)
				for (int chR = 0; chR < 3; chR++)
					dp[l][r][chL][chR] = INF; 
}

void calc() {
	for (int r = 1; r <= n; r++) {
		for (int l = r; l >= 1; l--) {
			if (l == r) {
				dp[l][r][a[l]][a[l]] = 0;
				continue;
			}

			for (int chL = 0; chL < 3; chL++) {
				for (int chR = 0; chR < 3; chR++) {
					if (chL != a[r]) {
						chkmin(dp[l][r][a[r]][chR], dp[l][r - 1][chL][chR] + (r - l));
					}
					if (chR != a[l]) {
						chkmin(dp[l][r][chL][a[r]], dp[l + 1][r][chL][chR] + (r - l));
					}
				}
			}

			for (int chL = 0; chL < 3; chL++) {
				for (int chR = 0; chR < 3; chR++) {
					for (int mid = l; mid < r; mid++) {
						for (int chMid_L = 0; chMid_L < 3; chMid_L++) {
							for (int chMid_R = 0; chMid_R < 3; chMid_R++) {
								if (chMid_L == chMid_R) continue;
								chkmin(dp[l][r][chL][chR], dp[l][mid][chL][chMid_L] + dp[mid + 1][r][chMid_R][chR]);
							}
						}
					}
				}
			}
		}
	}
}

int ans;

void make_ans() {
	ans = INF;
	for (int chL = 0; chL < 3; chL++) {
		for (int chR = 0; chR < 3; chR++) {
			chkmin(ans, dp[1][n][chL][chR]);
		}
	}
	if (ans == INF) ans = -1;
}

void run() {
	build();
	calc();
	make_ans();
}

void write() {
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
} 

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25