| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1275192 | nanaseyuzuki | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mn = 405 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e18, base = 311;
int n, prefix[mn][3];
string s;
vector <int> pos[mn];
int dp[405][405][405][5];
int f(int i, int j, int k, int pre){
if(i + j + k == n) return 0;
if(dp[i][j][k][pre] != -1) return dp[i][j][k][pre];
dp[i][j][k][pre] = inf;
for(int nxt = 0; nxt <= 2; nxt ++){
if(nxt == pre) continue;
int cost = 0;
int p, newi, newj, newk;
if(nxt == 0){
if(i + 1 > pos[nxt].size() - 1) continue;
p = pos[0][i + 1];
newi = i + 1, newj = j, newk = k;
}
if(nxt == 1){
if(j + 1 > pos[nxt].size() - 1) continue;
p = pos[nxt][j + 1];
newi = i, newj = j + 1, newk = k;
}
if(nxt == 2){
if(k + 1 > pos[nxt].size() - 1) continue;
p = pos[2][k + 1];
newi = i, newj = j, newk = k + 1;
}
for(int col = 0; col <= 2; col ++){
if(col == nxt) continue;
if(col == 0) cost += max(0ll, prefix[p][col] - i);
if(col == 1) cost += max(0ll, prefix[p][col] - j);
if(col == 2) cost += max(0ll, prefix[p][col] - k);
}
dp[i][j][k][pre] = min(dp[i][j][k][pre], f(newi, newj, newk, nxt) + cost);
}
return dp[i][j][k][pre];
}
void solve(){
cin >> n >> s;
s = "#" + s;
for(int i = 0; i <= 2; i++) pos[i].push_back(0);
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 2; j++) prefix[i][j] = prefix[i - 1][j];
if(s[i] == 'G'){
prefix[i][0] ++;
pos[0].push_back(i);
}
if(s[i] == 'R'){
prefix[i][1] ++;
pos[1].push_back(i);
}
if(s[i] == 'Y'){
prefix[i][2] ++;
pos[2].push_back(i);
}
}
for(int i = 0; i <= pos[0].size() - 1; i ++){
for(int j = 0; j <= pos[1].size() - 1; j++){
for(int k = 0; k <= pos[2].size() - 1; k++){
for(int pre = 0; pre <= 3; pre ++){
dp[i][j][k][pre] = -1;
}
}
}
}
cout << f(0, 0, 0, 4) << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}