TopCoder SRM 612, Division 2, Level 2 : EmoticonsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13041&rd=15845

問題概要

　丁度一つの顔文字を含むテキストファイルを、次の二種類の操作によって編集する。

• バッファにある全ての文字列をクリップボードにコピーする
• クリップボードの文字列をバッファにペーストする

それぞれの操作には 1 秒の時間が掛かる。顔文字の数を smiles にするために必要な時間の最小を求めよ。

解法

　各段階で二つの操作のいずれかを選択できるので、愚直にやると状態数が膨大になってしまいます。しかし、バッファにある顔文字の数とクリップボードにある顔文字の数が共に等しい状態が複数あったとすると、その内手数最小でないものから、最終的な最適手順に到達することはできません。従って、そのような状態から遷移する状態は考慮する必要が無いということになります。また、Division 1, Level 1 とは違って顔文字を削除する機能が無いので、バッファ・クリップボードのどちらの顔文字の数も単調増加します。
　( バッファの顔文字の数, クリップボードの顔文字の数 ) の組によって状態を識別するとします。上記より状態遷移が循環しないので、次のような DP を考えることができます。

• dp[ バッファの顔文字が i 個 ][ クリップボードの顔文字が j 個 ] := ここに至る最小の手数

dp[ i ][ j ] からの状態遷移は、コピーかペーストのいずれかなので、

• dp[ i + j ][ j ] を更新
• dp[ i ][ i ] を更新

の二通りです。計算が終わった後、dp[ smiles ] の最小値が問題への答えとなっています。

コード

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 EmoticonsDiv2
{
public:
	int printSmiles( int smiles )
	{
		VVI dp( 2000, VI( 2000, INF ) );
		dp[1][0] = 0;

		REP( i, 0, 2000 )
		{
			REP( j, 0, 2000 )
			{
				if ( i + j < 2000 )
				{
					dp[ i + j ][j] = min( dp[ i + j ][j], dp[i][j] + 1 );
				}
				{
					dp[i][i] = min( dp[i][i], dp[i][j] + 1 );
				}
			}
		}

		return *min_element( ALL( dp[ smiles ] ) );
	}
};