제출 #1333560

#제출 시각아이디문제언어결과실행 시간메모리
1333560penguin133Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
75 / 100
683 ms512792 KiB
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
int n;
char a[405];
int b[405];
vector <int> v[4];

int memo[405][405][405][4];

int dp(int x, int r, int g, int l) {
    if (x == n + 1) return 0;
    if (memo[x][r][g][l] != -1) return memo[x][r][g][l];
    //cerr << x << ' ' << r << ' ' << g << ' ' << l << '\n';
    int b = x - r - g - 1;
    int ans = 1e9;
    for (int i = 1; i <= 3; i++) {
        if (i == l) continue;
        if (i == 1 && r == sz(v[1])) continue;
        if (i == 2 && g == sz(v[2])) continue;
        if (i == 3 && b == sz(v[3])) continue;
        int pos;
        if (i == 1) {
            pos = v[1][r];
            int idx = upper_bound(v[2].begin(), v[2].end(), pos) - v[2].begin();
            int idx2 = upper_bound(v[3].begin(), v[3].end(), pos) - v[3].begin();
            //cerr << idx << ' ' << idx2 << '\n';
            pos += max(0, g - idx) + max(0, b - idx2);
            ans = min(ans, pos - x + dp(x + 1, r + 1, g, 1));
        }
        else if (i == 2) {
            pos = v[2][g];
            int idx = upper_bound(v[1].begin(), v[1].end(), pos) - v[1].begin();
            int idx2 = upper_bound(v[3].begin(), v[3].end(), pos) - v[3].begin();
            pos += max(0, r - idx) + max(0, b - idx2);
            ans = min(ans, pos - x + dp(x + 1, r, g + 1, 2));
        }
        else {
            pos = v[3][b];
            int idx = upper_bound(v[2].begin(), v[2].end(), pos) - v[2].begin();
            int idx2 = upper_bound(v[1].begin(), v[1].end(), pos) - v[1].begin();
            pos += max(0, g - idx) + max(0, r - idx2);
            ans = min(ans, pos - x + dp(x + 1, r, g, 3));
        }
        assert(pos>=x);
    }
    return memo[x][r][g][l] = ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 'R')b[i] = 1;
        else if (a[i] == 'G') b[i] = 2;
        else b[i] = 3;
        v[b[i]].push_back(i);
    }
    //memset(memo, -1, sizeof(memo));
    //int res = dp(1, 0, 0, 0);
    //cout << (res==1e9?-1:res);
    //wtf have to code bottom down dp

    for (int i = 0; i <= sz(v[1]); i++) {
        for (int j = 0; j <= sz(v[2]); j++) {
            for (int k = 0; k <= 3; k++) memo[n + 1][i][j][k] = 0;
        }
    }
    for (int x = n; x >= 1; x--) {
        for (int r = sz(v[1]); r >= 0; r--) {
            for (int g = sz(v[2]); g >= 0; g--) {
                for (int l = 0; l <= 3; l++) {
                    if (r + g > x - 1 || x - r - g - 1 > sz(v[3])) {
                        memo[x][r][g][l] = 1e9;
                        continue;
                    }
                    int b = x - r - g - 1;
                    int ans = 1e9;
                    for (int i = 1; i <= 3; i++) {
                        if (i == l) continue;
                        if (i == 1 && r == sz(v[1])) continue;
                        if (i == 2 && g == sz(v[2])) continue;
                        if (i == 3 && b == sz(v[3])) continue;
                        int pos;
                        if (i == 1) {
                            pos = v[1][r];
                            int idx = upper_bound(v[2].begin(), v[2].end(), pos) - v[2].begin();
                            int idx2 = upper_bound(v[3].begin(), v[3].end(), pos) - v[3].begin();
                            //cerr << idx << ' ' << idx2 << '\n';
                            pos += max(0, g - idx) + max(0, b - idx2);
                            ans = min(ans, pos - x + memo[x + 1][r + 1][g][1]);
                        }
                        else if (i == 2) {
                            pos = v[2][g];
                            int idx = upper_bound(v[1].begin(), v[1].end(), pos) - v[1].begin();
                            int idx2 = upper_bound(v[3].begin(), v[3].end(), pos) - v[3].begin();
                            pos += max(0, r - idx) + max(0, b - idx2);
                            ans = min(ans, pos - x + memo[x + 1][r][g + 1][2]);
                        }
                        else {
                            pos = v[3][b];
                            int idx = upper_bound(v[2].begin(), v[2].end(), pos) - v[2].begin();
                            int idx2 = upper_bound(v[1].begin(), v[1].end(), pos) - v[1].begin();
                            pos += max(0, g - idx) + max(0, r - idx2);
                            ans = min(ans, pos - x + memo[x + 1][r][g][3]);
                        }
                        assert(pos>=x);
                    }
                    memo[x][r][g][l] = ans;
                }
            }
        }
    }
    cout << (memo[1][0][0][0] == 1e9 ? -1 : memo[1][0][0][0]);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...