Submission #533622

#	Time	Username	Problem	Language	Result	Execution time	Memory
533622		alvingogo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	735 ms	6096 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

const int inf=1e9;
int dp[405][405][3][3];
int getdp(int x,int y,int p,int q){
	if(x>y){
		return 0;
	}
	return dp[x][y][p][q];
}
int main(){
	AquA;
	for(int i=0;i<405;i++){
		for(int j=0;j<405;j++){
			for(int p=0;p<3;p++){
				for(int q=0;q<3;q++){
					dp[i][j][p][q]=inf;
				}
			}
		
		}
	}
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		if(s[i]=='R'){
			v[i]=0;
		}
		else if(s[i]=='G'){
			v[i]=1;
		}
		else{
			v[i]=2;
		}
	}
	for(int t=1;t<=n;t++){
		for(int l=0;l+t-1<n;l++){
			int r=l+t-1;
			if(t==1){
				dp[l][r][v[l]][v[r]]=0;
			}
			else{
				for(int p=0;p<3;p++){
					for(int q=0;q<3;q++){
						if(v[l]==p){
							for(int a=0;a<3;a++){
								if(a!=v[l]){
									dp[l][r][p][q]=min(dp[l][r][p][q],getdp(l+1,r,a,q));
								}
							}
						}
						if(v[l]==q){
							for(int a=0;a<3;a++){
								if(a!=v[l]){
									dp[l][r][p][q]=min(dp[l][r][p][q],getdp(l+1,r,p,a)+r-l);
								}
							}
						}
						int y=0;
						for(int m=l+1;m<r;m++){
							if(v[m]!=v[l]){
								y++;
							}
							for(int u=0;u<3;u++){
								if(u!=v[l]){
									for(int z=0;z<3;z++){
										if(z!=v[l]){
											dp[l][r][p][q]=min(dp[l][r][p][q],y+getdp(l+1,m,p,u)+getdp(m+1,r,z,q));
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	/*
	for(int i=0;i<n;i++){
		for(int j=i;j<=n;j++){
			for(int p=0;p<3;p++){
				for(int q=0;q<3;q++){
					if(dp[i][j][p][q]!=inf){
						cout << i << " " << j << " " << p << " " << q << " " << dp[i][j][p][q] << "\n";
					}
				}
			}
		}
	}
	*/
	int ans=inf;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			ans=min(ans,dp[0][n-1][i][j]);
		}
	}
	if(ans==inf){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}
	return 0;
}

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