제출 #256400

#제출 시각아이디문제언어결과실행 시간메모리
256400Osama_AlkhodairyGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
75 / 100
573 ms757752 KiB
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 401;

int n, dp[N][N][N][3], sum[N][3], pos[N][3];
string s;

int get_sum(int idx, int l, int r){
    if(r < l || l == -1 || r == -1) return 0;
    return sum[r][idx] - (l == 0 ? 0 : sum[l - 1][idx]);
}
bool check(int a, int b, int c){
    if(a > c) swap(a, c);
    if(b > c) swap(b, c);
    if(a > b) swap(a, b);
    if(a + b + 1 < c) return 0;
    return 1;
}
int solve(int a, int b, int c, int las){
    if(!check(a, b, c)) return 1e9;
    if(a + b + c == n) return 0;
    int &ret = dp[a][b][c][las];
    if(ret != -1) return ret;
    ret = 1e9;
    if((las != 0 || a + b + c == 0) && pos[a][0] != -1){
        ret = min(ret, solve(a + 1, b, c, 0) + get_sum(1, pos[b][1], pos[a][0]) + get_sum(2, pos[c][2], pos[a][0]));
    }
    if((las != 1 || a + b + c == 0) && pos[b][1] != -1){
        ret = min(ret, solve(a, b + 1, c, 1) + get_sum(0, pos[a][0], pos[b][1]) + get_sum(2, pos[c][2], pos[b][1]));
    }
    if((las != 2 || a + b + c == 0) && pos[c][2] != -1){
        ret = min(ret, solve(a, b, c + 1, 2) + get_sum(0, pos[a][0], pos[c][2]) + get_sum(1, pos[b][1], pos[c][2]));
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(pos, -1, sizeof pos);
    memset(dp, -1, sizeof dp);
    cin >> n >> s;
    for(int i = 0 ; i < n ; i++){
        if(s[i] == 'R') s[i] = 0;
        else if(s[i] == 'G') s[i] = 1;
        else s[i] = 2;
        for(int j = 0 ; j < 3 ; j++){
            if(i > 0) sum[i][j] = sum[i - 1][j];
            sum[i][j] += s[i] == j;
        }
    }
    int pt0 = 0, pt1 = 0, pt2 = 0;
    for(int i = 0 ; i < n ; i++){
        if(s[i] == 0) pos[pt0++][0] = i;
        else if(s[i] == 1) pos[pt1++][1] = i;
        else pos[pt2++][2] = i;
    }
    int ans = solve(0, 0, 0, 0);
    if(ans == 1e9) ans = -1;
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...