Submission #396078

#	Time	Username	Problem	Language	Result	Execution time	Memory
396078		qwerasdfzxcl	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	116 ms	154224 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int dp[404][202][202][3], val[404][202][202][3];
vector<int> pos[3];
string s;

int f(char x){
    if (x=='R') return 0;
    else if (x=='G') return 1;
    else if (x=='Y') return 2;
    return -1;
}

bool CHK(int i, int j, int k, int z){
    int l = i-j-k;
    i--;
    if (z==0) j--;
    else if (z==1) k--;
    else if (z==2) l--;
    if (j<0 || k<0 || l<0) return 0;
    if (j*2>i+1 || k*2>i+1 || l*2>i+1) return 0;
    return 1;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n >> s;
    for (int i=0;i<n;i++){
        pos[f(s[i])].push_back(i);
    }
    int r = pos[0].size(), g = pos[1].size(), y = pos[2].size();
    if (r*2>n+1 || g*2>n+1 || y*2>n+1){
        printf("-1\n");
        return 0;
    }
    bool chk1=1;
    for (int i=1;i<n;i++) if (s[i]==s[i-1]) chk1=0;
    if (chk1){
        printf("0\n");
        return 0;
    }
    if (!pos[0].empty()) dp[1][1][0][0] = val[1][1][0][0] = pos[0][0];
    if (!pos[1].empty()) dp[1][0][1][1] = val[1][0][1][1] = pos[1][0];
    if (!pos[2].empty()) dp[1][0][0][2] = val[1][0][0][2] = pos[2][0];
    for (int i=2;i<=n;i++){
        for (int j=0;j<=min(i, r);j++){
            for (int k=0;k<=min(i, g);k++){
                int l = i-j-k;
                if (l>y) continue;
                if (l<0) break;
                if (j){
                    if (!k && !l) val[i][j][k][0] = pos[0][i-1]-i+1;
                    else if (k) val[i][j][k][0] = val[i-1][j][k-1][0] - (pos[1][k-1]<pos[0][j-1]);
                    else val[i][j][k][0] = val[i-1][j][k][0] - (pos[2][l-1]<pos[0][j-1]);
                }
                if (k){
                    if (!j && !l) val[i][j][k][1] = pos[1][i-1]-i+1;
                    else if (j) val[i][j][k][1] = val[i-1][j-1][k][1] - (pos[0][j-1]<pos[1][k-1]);
                    else val[i][j][k][1] = val[i-1][j][k][1] - (pos[2][l-1]<pos[1][k-1]);
                }
                if (l){
                    if (!j && !k) val[i][j][k][2] = pos[2][i-1]-i+1;
                    else if (j) val[i][j][k][2] = val[i-1][j-1][k][2] - (pos[0][j-1]<pos[2][l-1]);
                    else val[i][j][k][2] = val[i-1][j][k-1][2] - (pos[1][k-1]<pos[2][l-1]);
                }
            }
        }
        /*printf(" %d\n", i);
        for (int z=0;z<3;z++){
            for (int j=0;j<=r;j++){
                for (int k=0;k<=g;k++) printf("%d ", val[i][j][k][z]);
                printf("\n");
            }
            printf("\n");
        }
        printf("\n");*/
    }
    ///dp 계산
    for (int i=2;i<=n;i++){
        for (int j=0;j<=min(i, r);j++){
            if (j*2>i+1) break;
            for (int k=0;k<=min(i, g);k++){
                if (k*2>i+1 || j+k>i) break;
                int l = i-j-k;
                if (l>y || l*2>i+1) continue;
                if (l<0) break;
                if (j){
                    int tmp1 = 1e9, tmp2 = 1e9;
                    if (CHK(i-1, j-1, k, 1)) tmp1 = dp[i-1][j-1][k][1];
                    if (CHK(i-1, j-1, k, 2)) tmp2 = dp[i-1][j-1][k][2];
                    if (min(tmp1, tmp2)!=1e9) dp[i][j][k][0] = min(tmp1, tmp2)+val[i][j][k][0];
                }
                if (k){
                    int tmp1 = 1e9, tmp2 = 1e9;
                    if (CHK(i-1, j, k-1, 0)) tmp1 = dp[i-1][j][k-1][0];
                    if (CHK(i-1, j, k-1, 2)) tmp2 = dp[i-1][j][k-1][2];
                    if (min(tmp1, tmp2)!=1e9) dp[i][j][k][1] = min(tmp1, tmp2)+val[i][j][k][1];
                }
                if (l){
                    int tmp1 = 1e9, tmp2 = 1e9;
                    if (CHK(i-1, j, k, 0)) tmp1 = dp[i-1][j][k][0];
                    if (CHK(i-1, j, k, 1)) tmp2 = dp[i-1][j][k][1];
                    if (min(tmp1, tmp2)!=1e9) dp[i][j][k][2] = min(tmp1, tmp2)+val[i][j][k][2];
                }
            }
        }
        /*printf(" %d\n", i);
        for (int z=0;z<3;z++){
            for (int j=0;j<=r;j++){
                for (int k=0;k<=g;k++) printf("%d ", dp[i][j][k][z]);
                printf("\n");
            }
            printf("\n");
        }
        printf("\n");*/
    }
    int ans=1e9;
    for (int j=0;j<=r;j++){
        for (int k=0;k<=g;k++){
            for (int z=0;z<3;z++) if (dp[n][j][k][z]) ans = min(ans, dp[n][j][k][z]);
        }
    }
    cout << ans;
    /*while(true){
        int q, w, e, r;
        cin >> q >> w >>e >> r;
        if (q==-1) break;
        printf("%d %d %d\n", CHK(q, w, e, r), val[q][w][e][r], dp[q][w][e][r]);
    }*/
    return 0;
}

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