概要
三色のボールが一列に並んでいる。
次の操作を繰り返し適用して、列中の色の種類を一つにしたい。
- 左右いずれかの端のボールを取り除く
目標を達成するまでの操作回数の最小値を求めよ。
解法
最後に残す範囲を全通り試すことができます。
残す範囲が単一色であれば、その左右にあるボールの数で答えを更新していきます。
範囲が単一色かどうかは、その範囲を元に set のテンポラリオブジェクトを作って、サイズが 1 かどうかをみればよいです。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) class LittleElephantAndBallsAgain { public: int getNumber( string S ) { const int N = S.size(); int res = INT_MAX; REP( i, 0, N ) { REP( j, i + 1, N + 1 ) { if ( set<char>( S.begin() + i, S.begin() + j ).size() == 1 ) { res = min( res, i + ( N - j ) ); } } } return res; } };