제출 #97781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97781		Bodo171	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	60 / 100	560 ms	4344 KiB

joi2019_ho_t3

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=405;
int dp[2][nmax][nmax][3];
int ap[3],nr[3];
int p[3][nmax][3],a[3][nmax];
int n,i,j,k,use,oth,ch,nxt,ans;
string s;
int norm(char c)
{
    if(c=='R') return 0;
    if(c=='G') return 1;
    return 2;
}
int actual_pos(int wh)
{
   int ret=a[wh][ap[wh]];
   for(int oth=0;oth<3;oth++)
     if(oth!=wh)
        ret+=max(0,ap[oth]-p[wh][ap[wh]][oth]);
   return ret;
}
void prp(int &a,int b)
{
    a=min(a,b);
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>s;s=" "+s;
    for(i=1;i<=n;i++)
        a[norm(s[i])][++nr[norm(s[i])]]=i;
    for(i=0;i<3;i++)
        for(j=1;j<=nr[i];j++)
           for(oth=0;oth<3;oth++)
    {
        while(p[i][j][oth]<=nr[oth]&&a[oth][p[i][j][oth]]<a[i][j])
            p[i][j][oth]++;
        p[i][j][oth]--;
    }
    for(i=0;i<2;i++)
        for(j=0;j<=n;j++)
            for(k=0;k<=n;k++)
                for(ch=0;ch<3;ch++)
                  dp[i][j][k][ch]=(1<<30);
    for(i=0;i<3;i++)
        dp[0][0][0][i]=0;
    for(i=1;i<=n;i++)
    {
        use=1-use;
        for(j=0;j<=i-1;j++)
            for(k=0;k<=i-1-j;k++)
                for(ch=0;ch<3;ch++)
        {
            ap[0]=j;ap[1]=k;ap[2]=i-1-j-k;
            for(nxt=0;nxt<3;nxt++)
                if(nxt!=ch&&ap[nxt]<nr[nxt])
            {
                ap[nxt]++;
                prp(dp[use][ap[0]][ap[1]][nxt],dp[1-use][j][k][ch]+actual_pos(nxt)-i);
                ap[nxt]--;
            }
        }
        for(j=0;j<=i;j++)
            for(k=0;k<=i-j;k++)
                for(ch=0;ch<3;ch++)
        {
           dp[1-use][j][k][ch]=(1<<30);
        }
    }
    ans=(1<<30);
    for(i=0;i<3;i++)
        ans=min(ans,dp[use][nr[0]][nr[1]][i]);
    if(ans==(1<<30)) ans=-1;
    cout<<ans;
    return 0;
}

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