概要
一直線上の道があり、道は N 個の部分に分かれている。
各部分は左端から 0, 1, 2, ... と番号付けられる。
各部分には色がついていて、色は 'R', 'G', 'B' の三種類である。
位置 0 の色は 'R' である。
きつねは最初位置 0 にいて、位置 N - 1 まで移動したい。
移動はいくつかの step の連続となる。
距離 d の step では、コスト d * d をかけて、d 個右の部分に移動する。
また、'R' -> 'G' -> 'B' -> 'R' -> ... という順序で色を踏みたい。
位置 N - 1 に移動するために必要なコストの最小値を求めよ。
移動が不可能な場合は -1 で示せ。
解法
深く考えずに DP しました。
dp[ 位置 ] := 到達するための最小コスト
です。
各位置からは可能な step を全て試します。
コード
typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define MP( a, b ) make_pair( ( a ), ( b ) ) const int INF = INT_MAX / 2; map<char,char> nexts = { MP( 'R', 'G' ), MP( 'G', 'B' ), MP( 'B', 'R' ) }; class ColorfulRoad { public: int getMin( string road ) { const int N = road.size(); VI dp( N, INF ); dp[0] = 0; REP( i, 0, N - 1 ) { REP( j, i + 1, N ) { if ( road[j] == nexts[ road[i] ] ) { const int d = j - i; dp[j] = min( dp[j], dp[i] + d * d ); } } } return dp.back() == INF ? -1 : dp.back(); } };