#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <vector>
using namespace std;
#define INF 0x7f7f7f7f
int r, g, y;
vector<int> rv, gv, yv;
int dp[405][405][405][3];
int go(int rcnt, int gcnt, int ycnt, int pre)
{
if(rcnt == r-1 && gcnt == g-1 && ycnt == y-1)
return 0;
int& ret = dp[rcnt][gcnt][ycnt][pre];
if(ret != -1)
return ret;
ret = INF;
int val1 = 0, val2 = 0, val3 = 0;
if(rcnt+1 < r)
{
for(int i = 0; i < gcnt; i++)
if(rv[rcnt] < gv[i])
val1++;
for(int i = 0; i < ycnt; i++)
if(rv[rcnt] < yv[i])
val1++;
}
if(gcnt+1 < g)
{
for(int i = 0; i < rcnt; i++)
if(gv[gcnt] < rv[i])
val2++;
for(int i = 0; i < ycnt; i++)
if(gv[gcnt] < yv[i])
val2++;
}
if(ycnt+1 < y)
{
for(int i = 0; i < rcnt; i++)
if(yv[ycnt] < rv[i])
val3++;
for(int i = 0; i < gcnt; i++)
if(yv[ycnt] < gv[i])
val3++;
}
if(pre == 0)
{
if(gcnt+1 < g)
ret = min(ret, go(rcnt, gcnt+1, ycnt, 1) + abs(rcnt+gcnt+ycnt-(gv[gcnt]+val2)));
if(ycnt+1 < y)
ret = min(ret, go(rcnt, gcnt, ycnt+1, 2) + abs(rcnt+gcnt+ycnt-(yv[ycnt]+val3)));
}
else if(pre == 1)
{
if(rcnt+1 < r)
ret = min(ret, go(rcnt+1, gcnt, ycnt, 0) + abs(rcnt+gcnt+ycnt-(rv[rcnt]+val1)));
if(ycnt+1 < y)
ret = min(ret, go(rcnt, gcnt, ycnt+1, 2) + abs(rcnt+gcnt+ycnt-(yv[ycnt]+val3)));
}
else
{
if(rcnt+1 < r)
ret = min(ret, go(rcnt+1, gcnt, ycnt, 0) + abs(rcnt+gcnt+ycnt-(rv[rcnt]+val1)));
if(gcnt+1 < g)
ret = min(ret, go(rcnt, gcnt+1, ycnt, 1) + abs(rcnt+gcnt+ycnt-(gv[gcnt]+val2)));
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; string s;
cin >> n >> s;
for(int i = 0; i < n; i++)
{
if(s[i] == 'R')
{
r++;
rv.push_back(i);
}
else if(s[i] == 'G')
{
g++;
gv.push_back(i);
}
else
{
y++;
yv.push_back(i);
}
}
for(int i = 0; i <= r; i++)
for(int j = 0; j <= g; j++)
for(int k = 0; k <= y; k++)
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = -1;
int ans = min(go(0, 0, 0, 0), min(go(0, 0, 0, 1), go(0, 0, 0, 2)));
if(ans == INF)
cout << "-1\n";
else
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |