///In the name of GOD
//#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 400 + 10;
int n, cnt[3][MXN];
int dp[3][MXN][MXN][MXN];
vector<int> Pos[3];
string s;
int Calc(int ch, int a, int b, int c){
int now = 0, p = Pos[ch][(ch == 0 ? a : (ch == 1 ? b : c))];
int ta = cnt[0][p - 1], tb = cnt[1][p - 1], tc = cnt[2][p - 1];
now += max(0, ta - a);
now += max(0, tb - b);
now += max(0, tc - c);
return now;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n >> s;
s = "$" + s;
memset(dp, 31, sizeof dp);
for(int i = 1; i <= n; i ++){
switch(s[i]){
case 'R' : s[i] = 'A'; break;
case 'G' : s[i] = 'B'; break;
case 'Y' : s[i] = 'C'; break;
}
cnt[0][i] = cnt[0][i - 1];
cnt[1][i] = cnt[1][i - 1];
cnt[2][i] = cnt[2][i - 1];
cnt[s[i] - 'A'][i] ++;
Pos[s[i] - 'A'].push_back(i);
}
if(max({cnt[0][n], cnt[1][n], cnt[2][n]}) >= (n + 1) / 2)
return cout << -1, 0;
dp[0][1][0][0] = Calc(0, 0, 0, 0);
dp[1][0][1][0] = Calc(1, 0, 0, 0);
dp[2][0][0][1] = Calc(2, 0, 0, 0);
for(int a = 0; a <= cnt[0][n]; a ++){
for(int b = 0; b <= cnt[1][n]; b ++){
for(int c = 0; c <= cnt[2][n]; c ++){
if(a + b + c == 0) continue;
if(a < cnt[0][n]){
int* DP = &dp[0][a + 1][b][c];
(*DP) = min((*DP), dp[1][a][b][c] + Calc(0, a, b, c));
(*DP) = min((*DP), dp[2][a][b][c] + Calc(0, a, b, c));
}
if(b < cnt[1][n]){
int* DP = &dp[1][a][b + 1][c];
(*DP) = min((*DP), dp[0][a][b][c] + Calc(1, a, b, c));
(*DP) = min((*DP), dp[2][a][b][c] + Calc(1, a, b, c));
}
if(c < cnt[2][n]){
int* DP = &dp[2][a][b][c + 1];
(*DP) = min((*DP), dp[0][a][b][c] + Calc(2, a, b, c));
(*DP) = min((*DP), dp[1][a][b][c] + Calc(2, a, b, c));
}
}
}
}
int ans = dp[0][cnt[0][n]][cnt[1][n]][cnt[2][n]];
ans = min(ans, dp[1][cnt[0][n]][cnt[1][n]][cnt[2][n]]);
ans = min(ans, dp[2][cnt[0][n]][cnt[1][n]][cnt[2][n]]);
cout << ans << '\n';
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
427 ms |
809736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
427 ms |
809736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
440 ms |
809648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
427 ms |
809736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |