Submission #319656

#	Time	Username	Problem	Language	Result	Execution time	Memory
319656		CodeTiger927	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	478 ms	780520 KiB

joi2019_ho_t3

using namespace std;

#include <iostream>
#include <cstring>

#define MAXN 405

int dp[MAXN][MAXN][MAXN][3];
int N,prefix[MAXN][3],pos[MAXN][3],num[3];
string S;

inline int getNum(char c) {
	if(c == 'R') return 0;
	if(c == 'G') return 1;
	return 2;
}

int main() {
	cin >> N >> S;

	for(int i = 0;i < N;++i) {
		for(int j = 0;j < 3;++j) {
			prefix[i + 1][j] = prefix[i][j];
		}
		prefix[i + 1][getNum(S[i])]++;
		pos[++num[getNum(S[i])]][getNum(S[i])] = i + 1;
	}
	// 2139062143
	memset(dp,127,sizeof(dp));
	for(int i = 0;i < 3;++i) {
		dp[0][0][0][i] = 0;
	}
	for(int i = 0;i <= num[0];++i) {
		for(int j = 0;j <= num[1];++j) {
			for(int k = 0;k <= num[2];++k) {
				for(int pre = 0;pre < 3;++pre) {
					for(int next = 0;next < 3;++next) {
						if(next == pre || (next == 0 && i == num[0]) || (next == 1 && j == num[1]) || (next == 2 && k == num[2])) continue;
						int posA,posB,posC,other;
						if(pre == 0) {
							posA = pos[i][0];
							if(next == 1) {
								posB = pos[j + 1][1];
								posC = pos[k][2];
								other = 2;
							}else{
								posB = pos[k + 1][2];
								posC = pos[j][1];
								other = 1;
							}
						}else if(pre == 1) {
							posA = pos[j][1];
							if(next == 0) {
								posB = pos[i + 1][0];
								posC = pos[k][2];
								other = 2;
							}else{
								posB = pos[k + 1][2];
								posC = pos[i][0];
								other = 0;
							}
						}else{
							posA = pos[k][2];
							if(next == 1) {
								posB = pos[j + 1][1];
								posC = pos[i][0];
								other = 0;
							}else{
								posB = pos[i + 1][0];
								posC = pos[j][1];
								other = 1;
							}
						}
						int total = max(0,prefix[posB][pre] - prefix[posA][pre]) + max(0,prefix[posB][other] - prefix[posC][other]) + dp[i][j][k][pre];
						if(next == 0) {
							dp[i + 1][j][k][next] = min(dp[i + 1][j][k][next],total);
						}else if(next == 1) {
							dp[i][j + 1][k][next] = min(dp[i][j + 1][k][next],total);
						}else{
							dp[i][j][k + 1][next] = min(dp[i][j][k + 1][next],total);
						}
					}
				}
			}
		}
	}

	int ans = 2139062143;
	for(int i = 0;i < 3;++i) {
		ans = min(ans,dp[num[0]][num[1]][num[2]][i]);
	}
	cout << (ans == 2139062143 ? -1 : ans) << endl;
	return 0;
}

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