Submission #123064

#	Time	Username	Problem	Language	Result	Execution time	Memory
123064		Alliance	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1081 ms	6268 KiB

joi2019_ho_t3

// In the Name of Allah
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 410;
const ll MOD = 1e9+7;
using namespace std;

int dp[MAX_N][MAX_N][3][3];
int a[MAX_N];
int n;

void readinput()
{
    cin >> n;
    string s;
    cin >> s;
    for(int i = 1;i<=n;++i)
    {
        if (s[i-1]=='R')
            a[i] = 0;
        else if (s[i-1]=='G')
            a[i] = 1;
        else
            a[i] = 2;
    }
}

void mini(int &a,int b)
{
    a = min(a,b);
}

int main()
{
    readinput();
    for(int i = 0;i<MAX_N;++i)
        for(int j = 0;j<MAX_N;++j)
            for(int t = 0;t<3;++t)
                for(int k = 0;k<3;++k)
                    dp[i][j][t][k] = 1e9;
    for(int i = 1;i<=n;++i)
        dp[i][i][a[i]][a[i]] = 0;
    for(int i = 2;i<=n;++i)
    {
        for(int l = 1;l<=n-i+1;++l)
        {
            int r = l+i-1;
            for(int j = 0;j<3;++j)
            {
                for(int t = 0;t<3;++t)
                {
                    if (a[r]==t)
                    {
                        for(int x = 0;x<3;++x)
                        {
                            if (x!=a[r])
                                mini(dp[l][r][j][t],dp[l][r-1][j][x]);
                        }
                    }
                    if (a[r]==j)
                    {
                        for(int x = 0;x<3;++x)
                        {
                            if (x!=a[r])
                                mini(dp[l][r][j][t],dp[l][r-1][x][t]+r-l);
                        }
                    }
                    for(int k = 1;k<r-l;++k)
                    {
                        for(int u = 0;u<3;++u)
                        {
                            if (u==a[r])
                                continue;
                            for(int v = 0;v<3;++v)
                            {
                                if (v==a[r])
                                    continue;
                                mini(dp[l][r][j][t],dp[l][l+k-1][j][u]+dp[l+k][r-1][v][t]+r-l-k);
                            }
                        }
                    }
                }
            }
        }
    }
    vector<int> vc;
    for(int i = 0;i<3;++i)
    {
        for(int j = 0;j<3;++j)
        {
            if (dp[1][n][i][j]<=n*n)
                vc.push_back(dp[1][n][i][j]);
        }
    }
    if (!vc.size())
        return cout << -1,0;
    sort(vc.begin(),vc.end());
    cout << vc[0];
    return 0;
}

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