제출 #256418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256418		Osama_Alkhodairy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	489 ms	757556 KiB

joi2019_ho_t3

#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]);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(pos, -1, sizeof pos);
    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;
    vector <int> cnt(3);
    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;
        cnt[s[i]]++;
    }
    for(int a = 0 ; a <= n ; a++){
        for(int b = 0 ; b <= n ; b++){
            for(int c = 0 ; c <= n ; c++){
                for(int las = 0 ; las < 3 ; las++){
                    dp[a][b][c][las] = 1e9;
                }
            }
        }
    }
    for(int las = 0 ; las < 3 ; las++){
        dp[0][0][0][las] = 0;
    }
    for(int a = 0 ; a <= cnt[0] ; a++){
        for(int b = 0 ; b <= cnt[1] ; b++){
            for(int c = 0 ; c <= cnt[2] ; c++){
                for(int las = 0 ; las < 3 ; las++){
                    if((las != 0 || a + b + c == 0) && pos[a][0] != -1){
                        dp[a + 1][b][c][0] = min(dp[a + 1][b][c][0], dp[a][b][c][las] + 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){
                        dp[a][b + 1][c][1] = min(dp[a][b + 1][c][1], dp[a][b][c][las] + 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){
                        dp[a][b][c + 1][2] = min(dp[a][b][c + 1][2], dp[a][b][c][las] + get_sum(0, pos[a][0], pos[c][2]) + get_sum(1, pos[b][1], pos[c][2]));
                    }
                }
            }
        }
    }
    int ans = min(min(dp[cnt[0]][cnt[1]][cnt[2]][0], dp[cnt[0]][cnt[1]][cnt[2]][1]), dp[cnt[0]][cnt[1]][cnt[2]][2]);
    if(ans == 1e9) ans = -1;
    cout << ans << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25