제출 #1097858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097858		TrinhKhanhDung	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	152 ms	134736 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 403;

int N;
string s;
int pre[3][MAX];
vector<int> pos[MAX];
vector<vector<vector<vector<int>>>> dp;

int convert(char kt){
    if(kt == 'R') return 0;
    if(kt == 'G') return 1;
    if(kt == 'Y') return 2;
    return 2;
}

void solve(){
    cin >> N >> s;
    s = " " + s;
    for(int i = 1; i <= N; i++){
        int t = convert(s[i]);
        pos[t].push_back(i);
        for(int j = 0; j < 3; j++) pre[j][i] = pre[j][i - 1];
        pre[t][i]++;
    }

    dp.resize(sz(pos[0]) + 1, vector<vector<vector<int>>>(sz(pos[1] ) + 1, vector<vector<int>>(sz(pos[2]) + 1, vector<int>(3, INF))));
    for(int i = 0; i < 3; i++) dp[0][0][0][i] = 0;

    for(int i = 0; i <= sz(pos[0]); i++){
        for(int j = 0; j <= sz(pos[1]); j++){
            for(int k = 0; k <= sz(pos[2]); k++){
                for(int p = 0; p < 3; p++) if(dp[i][j][k][p] < INF){
                    if(p != 0 && i < sz(pos[0])){
                        int cost1 = max(pre[1][pos[0][i]] - j, 0);
                        int cost2 = max(pre[2][pos[0][i]] - k, 0);
                        minimize(dp[i + 1][j][k][0], dp[i][j][k][p] + cost1 + cost2);
                    }

                    if(p != 1 && j < sz(pos[1])){
                        int cost1 = max(pre[0][pos[1][j]] - i, 0);
                        int cost2 = max(pre[2][pos[1][j]] - k, 0);
                        minimize(dp[i][j + 1][k][1], dp[i][j][k][p] + cost1 + cost2);
                    }

                    if(p != 2 && k < sz(pos[2])){
                        int cost1 = max(pre[0][pos[2][k]] - i, 0);
                        int cost2 = max(pre[1][pos[2][k]] - j, 0);
                        minimize(dp[i][j][k + 1][2], dp[i][j][k][p] + cost1 + cost2);
                    }
                }
            }
        }
    }

    int ans = INF;
    for(int i = 0; i < 3; i++) minimize(ans, dp[sz(pos[0])][sz(pos[1])][sz(pos[2])][i]);
    if(ans >= INF) ans = -1;
    cout << ans << '\n';
}

//nhan xet: vi tri cung mau nhau sau khi sap xep van nam theo 1 thu tu
//ta dua lan luot cac mau va duoi day da tao

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("deggraph.inp", "r", stdin);
//    freopen("deggraph.out", "w", stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

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