제출 #1369945

#제출 시각아이디문제언어결과실행 시간메모리
1369945memaygayGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
296 ms766716 KiB
# include <bits/stdc++.h>
using namespace std;
int n,pos[405][5],cnt[5],dp[405][405][405][3],pref[405][3];
string s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;
    s = '#' + s;
    for (int i =1; i <= n; i++)
    {
        if (s[i]=='R')
        {
            cnt[0]++;
            pos[cnt[0]][0] = i;
            pref[i][0] ++;
        }
        else if (s[i]=='G')
        {
            cnt[1] ++;
            pos[cnt[1]][1]=i;
            pref[i][1]++;
        }
        else
        {
            cnt[2]++;
            pos[cnt[2]][2]= i;
            pref[i][2]++;
        }
        pref[i][0] += pref[i-1][0];
        pref[i][1] += pref[i-1][1];
        pref[i][2] += pref[i-1][2];
    }
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) for (int p = 0; p <= 2; p++)dp[i][j][k][p]=1e9;
    dp[0][0][0][0] = 0;
    dp[0][0][0][1]=0;
    dp[0][0][0][2] = 0;
    for (int cnt0 = 0; cnt0 <= pref[n][0]; cnt0++)
    {
        for (int cnt1 = 0; cnt1 <= pref[n][1]; cnt1++)
        {
            for (int cnt2 = 0; cnt2 <= pref[n][2]; cnt2++)
            {
                for (int color = 0; color < 3; color++)
                {
                    if (dp[cnt0][cnt1][cnt2][color] != 1e9)
                    {
                        for (int ncolor = 0; ncolor < 3; ncolor++)
                        {
                            if (ncolor==color) continue;
                            int conlai = 3-color-ncolor;
                            int b[3] = {cnt0,cnt1,cnt2};
                            b[ncolor]++;
                            int end = pos[b[ncolor]][ncolor];
                            dp[b[0]][b[1]][b[2]][ncolor]= min(dp[b[0]][b[1]][b[2]][ncolor],dp[cnt0][cnt1][cnt2][color] + end-1 - min(cnt0, pref[end][0]) - min(cnt1,pref[end][1])-min(cnt2,pref[end][2]));
                        }
                    }
                }
            }
        }
    }
    int res = min({dp[pref[n][0]][pref[n][1]][pref[n][2]][0],dp[pref[n][0]][pref[n][1]][pref[n][2]][1],dp[pref[n][0]][pref[n][1]][pref[n][2]][2]});
    if (res==1e9)
    {
        cout << -1;
    }
    else cout << res;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…