TopCoder SRM 565, Divison 2, Level 2 : MonstersValley2

概要

いくつかのモンスターが居る丘を通りたい。
モンスターと戦うことはセず、いくらかのお金を払ってモンスターを買収することとする。
買収したモンスターの怖さの合計値より高い怖さをもつモンスターは、必ず買収しなければならない。
それ以外の場合、そのモンスターは素通りしてもよい。
各モンスターの怖さと買収に必要な金額が与えられるので、必要な資金の最小額を答えよ。

解法

モンスターの数が 20 と小さいので、この部分をビットで全探索して、それぞれの場合についてシミュレーションします。
怖さの値域が大きいので、オーバーフローに注意です。（本番で七人ほど撃墜しました）

コード

typedef long long LL;

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

class MonstersValley2
{
public:
	int minimumPrice( vector <int> dread, vector <int> price )
	{
		const int N = dread.size();

		int res = INT_MAX;

		REP( flag, 0, 1 << N )
		{
			int p = 0;
			LL total = 0;
			bool ok = true;

			REP( i, 0, N )
			{
				if ( flag & ( 1 << i ) )
				{
					total += dread[i];
					p += price[i];
				}
				else if ( total < dread[i] )
				{
					ok = false;
					break;
				}
			}

			if ( ok )
			{
				res = min( res, p );
			}
		}

		return res;	
	}
};