TopCoder SRM 588, Division 2, Level 2 : GUMIAndSongsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12707&rd=15700

概要

N 個の曲があって、それぞれについて長さとトーンの情報が与えられる。
曲 x の次に曲 y を歌うとき、そのトーンの差の絶対値だけ時間を開けなければ歌えない。
時間 T 以内に歌うことのできる（異なる）曲の数の最大値を求めよ。
なお、N <= 15 である。

解法

N はある程度小さいですが、曲順の順列を総当りすると間に合いません。
しかし、「既に歌った曲がどれか」と「最後に歌った曲がどれか」が同一の状態のうち、所要時間が最小でないものは考慮する必要がありません。。
従って、次のような DP を考えることができます。
　dp[ 既に歌った曲の集合 ][ 最後に歌った曲 ] := 最小の所要時間
ここで、初期状態は各 i について
　dp[ 1 << i ][ i ] = duration[ i ]
です。
状態遷移は次のようになります。
　dp[ s ][ i ] から dp[ s | 1 << j ][ j ] を dp[ s ][ i ] + abs( tone[i] - tone[j] ) + duration[ j ] で更新
到達できる状態のうちで所要時間が T 以内のものについて s の立っているビットの数を数え、その最大値が答えです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = INT_MAX / 2;

class GUMIAndSongsDiv2
{
public:
	int maxSongs( vector <int> duration, vector <int> tone, int T )
	{
		const int N = duration.size();

		VVI dp( 1 << N, VI( N, INF ) );
		REP( i, 0, N )
		{
			dp[ 1 << i ][i] = duration[i];
		}

		REP( s, 0, 1 << N )
		{
			REP( i, 0, N )
			{
				REP( j, 0, N )
				{
					dp[ s | 1 << j ][j] = min( dp[ s | 1 << j ][j], dp[s][i] + abs( tone[i] - tone[j] ) + duration[j] );
				}
			}
		}

		int res = 0;
		REP( s, 0, 1 << N )
		{
			REP( i, 0, N )
			{
				if ( dp[s][i] <= T )
				{
					res = max( res, __builtin_popcount( s ) );
				}
			}
		}
		return res;
	}
};