SRM596_Div2_Level_2_ColorfulRoad.cpp

class ColorfulRoad {
private:
	int colorid(char ch) {
		switch(ch) {
			case 'R': return 0;
			case 'G': return 1;
			case 'B': return 2;
			default: return -1;
		}
	}

public:
  int getMin( string road ) {
  	const int INF = 1000000;
  	int n = (int)road.size();
  	vector<int> dp(n, INF);

  	dp[0] = 0;
  	for (int i=0; i<n ;++i) {
  		for (int j=i+1; j<n ;++j) {
  			if (colorid(road[j]) == (colorid(road[i]) + 1) % 3) {
  				dp[j] = min(dp[j], dp[i]+(j-i)*(j-i));
  			}
  		}
  	}

  	return dp[n-1] < INF ? dp[n-1] : -1;
  }
};