제출 #1324442

#제출 시각아이디문제언어결과실행 시간메모리
1324442sh_qaxxorov_571Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
1 ms332 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 1e9;
int dp[401][401][401][3];
int pos[3][401];
int pre[3][3][401][401];

int main() {
    int n;
    string s;
    cin >> n >> s;

    vector<int> cnt(3, 0);
    for (int i = 0; i < n; i++) {
        int c = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
        pos[c][++cnt[c]] = i + 1;
    }

    // Har bir rang uchun boshqa ranglarning nechtasi undan oldin kelishini hisoblash
    for (int c1 = 0; c1 < 3; c1++) {
        for (int c2 = 0; c2 < 3; c2++) {
            if (c1 == c2) continue;
            for (int i = 1; i <= cnt[c1]; i++) {
                int cur_pos = pos[c1][i];
                int c2_cnt = 0;
                for (int j = 1; j <= cnt[c2]; j++) {
                    if (pos[c2][j] < cur_pos) c2_cnt++;
                    pre[c1][c2][i][j] = c2_cnt;
                }
            }
        }
    }

    // DP jadvalini to'ldirish
    for (int i = 0; i <= cnt[0]; i++)
        for (int j = 0; j <= cnt[1]; j++)
            for (int k = 0; k <= cnt[2]; k++)
                for (int l = 0; l < 3; l++) dp[i][j][k][l] = INF;

    if (cnt[0] > 0) dp[1][0][0][0] = pos[0][1] - 1;
    if (cnt[1] > 0) dp[0][1][0][1] = pos[1][1] - 1;
    if (cnt[2] > 0) dp[0][0][1][2] = pos[2][1] - 1;

    for (int r = 0; r <= cnt[0]; r++) {
        for (int g = 0; g <= cnt[1]; g++) {
            for (int y = 0; y <= cnt[2]; y++) {
                for (int last = 0; last < 3; last++) {
                    if (dp[r][g][y][last] == INF) continue;

                    for (int next = 0; next < 3; next++) {
                        if (next == last) continue;
                        int nr = r + (next == 0), ng = g + (next == 1), ny = y + (next == 2);
                        if (nr > cnt[0] || ng > cnt[1] || ny > cnt[2]) continue;

                        int p = pos[next][(next == 0 ? nr : (next == 1 ? ng : ny))];
                        int cost = (p - 1) + max(0, nr - pre[next][0][(next == 0 ? nr : (next == 1 ? ng : ny))][cnt[0]])
                                         + max(0, ng - pre[next][1][(next == 0 ? nr : (next == 1 ? ng : ny))][cnt[1]])
                                         + max(0, ny - pre[next][2][(next == 0 ? nr : (next == 1 ? ng : ny))][cnt[2]])
                                         - (r + g + y);
                        // Soddaroq xarajat hisoblash:
                        int actual_cost = max(0, r - pre[next][0][(next==0?nr:(next==1?ng:ny))][cnt[0]]) +
                                          max(0, g - pre[next][1][(next==0?nr:(next==1?ng:ny))][cnt[1]]) +
                                          max(0, y - pre[next][2][(next==0?nr:(next==1?ng:ny))][cnt[2]]);
                        
                        dp[nr][ng][ny][next] = min(dp[nr][ng][ny][next], dp[r][g][y][last] + (p - 1 + actual_cost) - (r+g+y));
                    }
                }
            }
        }
    }

    int ans = 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]});
    cout << (ans >= INF ? -1 : ans) << endl;

    return 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...