제출 #156506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156506		vex	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	148 ms	163192 KiB

joi2019_ho_t3

///10:32
///10:55
///
#include<bits/stdc++.h>
#define INF 100000000
#define maxn 405
using namespace std;

map<char,int>br;
int n;
string s;
int dp[maxn][maxn][maxn][3];
int col[maxn][3];
int tot[3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    br['R']=0;
    br['G']=1;
    br['Y']=2;

    cin>>n;
    cin>>s;

    tot[0]=tot[1]=tot[2]=0;
    for(int i=0;i<n;i++)
    {
        int boja=br[s[i]];
        //cout<<boja<<" ";
        tot[boja]++;
        col[tot[boja]][boja]=i;
    }
    /*cout<<endl;

    for(int i=0;i<=2;i++)
    {
        cout<<tot[i]<<"  ";
        for(int j=1;j<=tot[i];j++)
        {
            cout<<col[j][i]<<" ";
        }
        cout<<endl;
    }*/



    int red[3];
    for(red[0]=0;red[0]<=tot[0];red[0]++)
    {
        for(red[1]=0;red[1]<=tot[1];red[1]++)
        {
            for(red[2]=0;red[2]<=tot[2];red[2]++)
            {
                for(int i=0;i<=2;i++)
                {
                    dp[ red[0] ][ red[1] ][ red[2] ][i]=INF;
                    if(red[i]==0)continue;

                    int poz=red[0]+red[1]+red[2]-1;
                    int dod=abs(col[red[i]][i]-poz);
                    int ost1=(i+1)%3;
                    int ost2=(i+2)%3;
                    if(poz==0)
                    {
                        dp[ red[0] ][ red[1] ][ red[2] ][i]=dod;
                        continue;
                    }

                    int tre[3];
                    for(int j=0;j<=2;j++)
                    {
                        tre[j]=red[j];
                    }
                    tre[i]--;


                    dp[ red[0] ][ red[1] ][ red[2] ][i]=min(dp[ red[0] ][ red[1] ][ red[2] ][i], dp[ tre[0] ][ tre[1] ][ tre[2] ][ost1] + dod);
                    dp[ red[0] ][ red[1] ][ red[2] ][i]=min(dp[ red[0] ][ red[1] ][ red[2] ][i], dp[ tre[0] ][ tre[1] ][ tre[2] ][ost2] + dod);
                }
            }
        }
    }

    int sol=INF;
    for(int i=0;i<=2;i++)
    {
        sol=min(sol,dp[ tot[0] ][ tot[1] ][ tot[2] ][i]);
    }

    if(sol>=INF)cout<<"-1"<<endl;
    else
    {
        sol/=2;
        cout<<sol<<endl;
    }

    return 0;
}

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