Submission #542061

#	Time	Username	Problem	Language	Result	Execution time	Memory
542061		Cookie197	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	231 ms	522776 KiB

joi2019_ho_t3

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>

using namespace std;
#define ll long long
#define endl "\n"
#define mp make_pair
#define out(x) cout<< #x << " = " << x << endl
#define pii pair<int,int> 
#pragma GCC optimize("Ofast")

// 考慮前i個，放了r個R g個G i-r-g個Y，第i個恰是R/G/Y，所需最小步數
string s;
int n;
vector<int> rpos, gpos, ypos;
int rcnt, gcnt, ycnt;
int dp[405][405][405][3];
int rpre[405],gpre[405],ypre[405];
void chmin(int &a, int b){
    a = min(a,b);
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>s;
    s = '$' + s;
    rpos.push_back(0), gpos.push_back(0), ypos.push_back(0);
    for (int i=1;i<=n;i++){
        if (s[i] == 'R') rpos.push_back(i), rcnt++;
        if (s[i] == 'G') gpos.push_back(i), gcnt++;
        if (s[i] == 'Y') ypos.push_back(i), ycnt++;
        rpre[i] = rpre[i-1] + (s[i] == 'R');
        gpre[i] = gpre[i-1] + (s[i] == 'G');
        ypre[i] = ypre[i-1] + (s[i] == 'Y');
    }

    for (int i=1;i<=n;i++) for (int r=0;r<=rcnt;r++) for (int g=0;g<=gcnt;g++) for (int c=0;c<=2;c++) dp[i][r][g][c] = 1e9;
    dp[1][1][0][0] = rcnt ? rpos[1] - 1 : 1e9;
    dp[1][0][1][1] = gcnt ? gpos[1] - 1 : 1e9;
    dp[1][0][0][2] = ycnt ? ypos[1] - 1 : 1e9;

    for (int i=1;i<n;i++) for (int r=0;r<=rcnt;r++) for (int g=0;g<=gcnt;g++) for (int c=0;c<=2;c++){
        int y = i-r-g; if (y<0) continue;
        if (dp[i][r][g][c] == 1e9) continue;
        if (r>i || g>i || y>i) continue;
        if (r+g > i) continue;
        //cout<<i<<" "<<r<<" "<<g<<" "<<y<<" "<<c<<"   "<<dp[i][r][g][c]<<endl;
        // put R in i+1
        if (c!=0 && r<rcnt){
            int cost = abs(gpre[rpos[r+1]] - g) + abs(ypre[rpos[r+1]] - y);
            chmin(dp[i+1][r+1][g][0], dp[i][r][g][c] + cost);
        }

        if (c!=1 && g<gcnt){
            int cost = abs(rpre[gpos[g+1]] - r) + abs(ypre[gpos[g+1]] - y);
            chmin(dp[i+1][r][g+1][1], dp[i][r][g][c] + cost);
        }

        if (c!=2 && y<ycnt){
            int cost = abs(rpre[ypos[y+1]] - r) + abs(gpre[ypos[y+1]] - g);
            chmin(dp[i+1][r][g][2], dp[i][r][g][c] + cost);
        }
    }

    int res = min(dp[n][rcnt][gcnt][0], min(dp[n][rcnt][gcnt][1], dp[n][rcnt][gcnt][2]));
    if (res >= 5e8) cout<<-1<<endl;
    else cout<<res/2<<endl;
}

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