解法
編集途中で取り得るそれぞれの状態は、( バッファにある顔文字の数, クリップボードにある顔文字の数 ) で一意に識別できます。これを ( n, m ) とすると、それぞれの操作による状態遷移は
- コピー:( n, m ) -> ( n, n )
- ペースト:( n, m ) -> ( n + m, m )
- 削除:( n, m ) -> ( n - 1, m )
という具合にパラメータが変化します。ここで、状態を頂点、状態遷移を辺とした有向グラフを考えることができます。このグラフ上で、( 1, 0 ) から ( smiles, x ) ( x は非負の整数 ) で表されるいずれかの頂点への最短路のうち、コスト最小のもの(のコスト)が答えとなります。辺の重みは一様に 1 なので、( 1, 0 ) からの BFS で単一始点最短路問題を解くことにより、問題の解を得ることができます。バッファの顔文字の数は無限に大きくすることが可能ですが、少なくとも smiles の二倍以上あると無駄なので [ 0, smiles * 2 ) の範囲だけ計算すればよいです。
コード
typedef vector<int> VI; typedef vector<VI> VVI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() const int INF = INT_MAX / 2; class EmoticonsDiv1 { public: int printSmiles( int smiles ) { VVI distances( smiles * 2, VI( smiles * 2, INF ) ); distances[1][0] = 0; typedef tuple<int,int,int> State; queue<State> que; que.push( State( 0, 1, 0 ) ); while ( !que.empty() ) { const int d = get<0>( que.front() ); const int n = get<1>( que.front() ); const int m = get<2>( que.front() ); que.pop(); // copy if ( d + 1 < distances[n][n] ) { distances[n][n] = d + 1; que.push( State( distances[n][n], n, n ) ); } // paste if ( n + m < smiles * 2 && d + 1 < distances[ n + m ][m] ) { distances[ n + m ][m] = d + 1; que.push( State( distances[ n + m ][m], n + m, m ) ); } // delete if ( 0 < n && d + 1 < distances[ n - 1 ][m] ) { distances[ n - 1 ][m] = d + 1; que.push( State( distances[ n - 1 ][m], n - 1, m ) ); } } return *min_element( ALL( distances[ smiles ] ) ); };