제출 #1363868

#제출 시각아이디문제언어결과실행 시간메모리
1363868NewtonabcGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
16 ms2116 KiB
#include<bits/stdc++.h>
using namespace std;
int p[3][410],dp[2][410][410][3],a[410],f[3][410],c[3];
int main(){
    int n; cin>>n;
    string s; cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='R') a[i+1]=0;
        else if(s[i]=='G') a[i+1]=1;
        else a[i+1]=2;
    }
    for(int i=1;i<=n;i++){
        f[a[i]][++c[a[i]]]=i;
        p[a[i]][i]++;
        for(int j=0;j<3;j++) p[j][i]+=p[j][i-1];
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<=p[1][n];j++){
            for(int k=0;k<=p[2][n];k++){
                dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=1e9;
            }
        }
    }
    int ans=INT_MAX;
    for(int i=0;i<=p[0][n];i++){
        int now=i&1;
        int pre=(i+1)&1;
        for(int j=0;j<=p[1][n];j++) for(int k=0;k<=p[2][n];k++) for(int x=0;x<3;x++) dp[now][j][k][x]=1e9;
        if(i==0) dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
        for(int j=0;j<=p[1][n];j++){
            for(int k=0;k<=p[2][n];k++){
                if(i==0 && j==0 && k==0) continue;
                if(i!=0){
                    int tmp=f[0][i],cd=0;
                    if(j<p[1][tmp]) cd+=p[1][tmp]-j;
                    if(k<p[2][tmp]) cd+=p[2][tmp]-k;
                    dp[now][j][k][0]=min(dp[now][j][k][0],min(dp[pre][j][k][1],dp[pre][j][k][2])+cd);
                }
                if(j!=0){
                    int tmp=f[1][j],cd=0;
                    if(i<p[0][tmp]) cd+=p[0][tmp]-i;
                    if(k<p[2][tmp]) cd+=p[2][tmp]-k;
                    dp[now][j][k][1]=min(dp[now][j][k][1],min(dp[now][j-1][k][0],dp[now][j-1][k][2])+cd);
                }
                if(k!=0){
                    int tmp=f[2][k],cd=0;
                    if(i<p[0][tmp]) cd+=p[0][tmp]-i;
                    if(j<p[1][tmp]) cd+=p[1][tmp]-j;
                    dp[now][j][k][2]=min(dp[now][j][k][2],min(dp[now][j][k-1][0],dp[now][j][k-1][1])+cd);
                }
                if(i==p[0][n] && j==p[1][n] && k==p[2][n]){
                    for(int x=0;x<3;x++){
                        ans=min(ans,dp[now][j][k][x]);
                    }
                }
            }
        }
    }
    if(ans>=1e9) cout<<-1;
    else cout<<ans;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…