제출 #1331752

#제출 시각아이디문제언어결과실행 시간메모리
1331752WarinchaiGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
208 ms188904 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<vector<vector<int>>>>dp;
int val[505];
int inf=1e15;
int cnt[505][5];
int num[5];
int pos[5][505];
int cur[5];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cerr<<"work\n";
    int n;cin>>n;
    string s;cin>>s;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='R')val[i]=1;
        else if(s[i-1]=='G')val[i]=2;
        else val[i]=3;
        num[val[i]]++;
        pos[val[i]][++cur[val[i]]]=i;
    }
    //cerr<<"work\n";
    dp.resize(num[1]+5,vector<vector<vector<int>>>(num[2]+5,vector<vector<int>>(num[3]+5,vector<int>(5))));
    for(int i=0;i<=num[1];i++)for(int j=0;j<=num[2];j++)for(int k=0;k<=num[3];k++)for(int l=1;l<=3;l++){
        dp[i][j][k][l]=inf;
    }
    dp[0][0][0][1]=dp[0][0][0][2]=dp[0][0][0][3]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++)cnt[i][j]=cnt[i-1][j];
        cnt[i][val[i]]++;
        //cerr<<cnt[i][1]<<' '<<cnt[i][2]<<" "<<cnt[i][3]<<"\n";
    }
    for(int i=0;i<=num[1];i++)for(int j=0;j<=num[2];j++)for(int k=0;k<=num[3];k++)for(int l=1;l<=3;l++)for(int m=1;m<=3;m++){
        if(l==m)continue;
        if(l==1){
            if(i==0)continue;
            int add=0;
            add+=max(0ll,cnt[pos[1][i]][2]-cnt[pos[2][j]][2]);
            add+=max(0ll,cnt[pos[1][i]][3]-cnt[pos[3][k]][3]);
            dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][m]+add);
        }else if(l==2){
            if(j==0)continue;
            int add=0;
            add+=max(0ll,cnt[pos[2][j]][1]-cnt[pos[1][i]][1]);
            add+=max(0ll,cnt[pos[2][j]][3]-cnt[pos[3][k]][3]);
            dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-1][k][m]+add);
        }else{
            if(k==0)continue;
            int add=0;
            add+=max(0ll,cnt[pos[3][k]][1]-cnt[pos[1][i]][1]);
            add+=max(0ll,cnt[pos[3][k]][2]-cnt[pos[2][j]][2]);
            dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j][k-1][m]+add);
        }
        //cerr<<"dp:"<<i<<' '<<j<<" "<<k<<' '<<l<<dp[i][j][k][l]<<"\n";
    }
    for(int i=0;i<=num[1];i++)for(int j=0;j<=num[2];j++)for(int k=0;k<=num[3];k++)for(int l=1;l<=3;l++){
        if(dp[i][j][k][l]==inf)continue;
        //cerr<<"dp:"<<i<<' '<<j<<" "<<k<<' '<<l<<": "<<dp[i][j][k][l]<<"\n";
    }
    int ans=min({dp[num[1]][num[2]][num[3]][1],dp[num[1]][num[2]][num[3]][2],dp[num[1]][num[2]][num[3]][3]});
    if(ans>=inf)cout<<"-1\n";
    else cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...