제출 #1342209

#제출 시각아이디문제언어결과실행 시간메모리
1342209NipphitchGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
1097 ms41660 KiB
#include <bits/stdc++.h>
using namespace std;
const int N=405;

int n,cntr,cntg,cnty;
vector <char> st;
map <vector <char>,int> dp;

int rec(vector <char> u,int w){
    if(w>n*(n-1)/2) return 1e9+7;
    if(dp.find(u)!=dp.end()) return dp[u];
    bool ok=true;
    for(int i=0;i<n;i++){
        if(i+1<n && u[i]==u[i+1]){
            ok=false;
            break;
        }
        if(i-1>0 && u[i]==u[i-1]){
            ok=false;
            break;
        }
    }
    if(ok) return dp[u]=w;
    int res=1e9;
    for(int i=0;i+1<n;i++){
        if(u[i]==u[i+1]) continue;
        swap(u[i],u[i+1]);
        res=min(res,rec(u,w+1));
        swap(u[i],u[i+1]);
    }
    return dp[u]=res;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        char c;
        cin >> c;
        st.push_back(c);
        if(c=='R') cntr++;
        else if(c=='G') cntg++;
        else cnty++;
    }
    if(cnty>(n+1)/2 || cntr>(n+1)/2 || cntg>(n+1)/2){
        cout << "-1";
        exit(0);
    }
    //dp[st]=0;
    cout << rec(st,0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...