제출 #988344

#제출 시각아이디문제언어결과실행 시간메모리
988344biximoGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
15 / 100
414 ms519360 KiB
#include <bits/stdc++.h>
#define N 405
#define INF 2000000000
using namespace std;
int n, dp[N][N][N][4], p[N][3];
string s;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    for(char&i: s) {
    	if(i=='R')i=0;
    	else if(i == 'G')i=1;
    	else i=2;
    }
    for(int i = 1; i <= n; i ++) {
    	for(int j = 0; j < 3; j ++) {
    		p[i][j] = p[i-1][j]+(s[i-1]==j);
    	}
    }
    for(int i = 0; i <= n; i ++) {
    	for(int j = 0; j <= i; j ++) {
    		for(int k = 0; j+k <= i; k ++) {
    			for(int l = 0; l < 4; l ++) {
    				dp[i][j][k][l] = INF;
    			}
    		}
    	}
    }
    dp[0][0][0][3] = 0;
    for(int i = 0; i < n; i ++) {
    	for(int j = 0; j <= i; j ++) {
    		for(int k = 0; j+k <= i; k ++) {
    			for(int l = 0; l < 3+(i==0); l ++) {
    				if(INF == dp[i][j][k][l]) continue;
    				for(int nl = 0; nl < 3; nl ++) {
    					if(l == nl) continue;
    					int nj = j, nk = k;
    					if(nl == 0) nj++;
    					else if(nl == 1) nk++;
    					int nc = dp[i][j][k][l]+(abs(p[i+1][0]-nj)+abs(p[i+1][1]-nk)+abs(p[i+1][2]-(i+1-nj-nk)))/2;
    					dp[i+1][nj][nk][nl] = min(dp[i+1][nj][nk][nl],nc);
    					assert((abs(p[i+1][0]-nj)+abs(p[i+1][1]-nk)+abs(p[i+1][2]-(i+1-nj-nk)))%2==0);
    				}
    			}
    		}
    	}
    }
    int ans = INF;
    for(int i = 0; i < 3; i ++) {
    	ans = min(ans, dp[n][p[n][0]][p[n][1]][i]);
    }
    // assert(ans%2==0);
    if(ans == INF) cout << "-1";
    else cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...