TopCoder SRM 605, Division 1, Level 1 : AlienAndHamburgers

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12948&rd=15838

問題概要

　N 個のハンバーガーがある。各ハンバーガーは二つの属性 type と taste をもち、それぞれ整数値で表される。
　これらのハンバーガーのうち、いくつかを選んで食べる。（食べた種類の数 × taste の合計）が最大となるように食べたときの、この値を求めよ。

解法

　まず、同じ種類のハンバーガーを複数食べるなら、taste の大きい方から選択した方が得になります。これは、taste が非負のものがあればそれらから選択した方が得であり、全て負の場合であって食べた種類数を増やす場合でも、その絶対値が小さいものを選択した方が得となることから分かります。
　次に、食べた種類の数が同一の状態が複数あったとき、全体の最適解に繋がるのは taste の総和が最大のものだけです。
　これらを踏まえると、次のような DP を考えることができます。

• dp[ i 種類考慮 ][ j 種類食べた ] := taste の総和の最大値

dp[ i ][ j ] からの更新は、type が i となるハンバーガーをいくつ食べるか全て試して、

• dp[ i + 1 ][ j + 1 ] を dp[ i ][ j ] + ( type が i のハンバーガーのうち、taste が大きい物から k 個とったときの taste の総和 ) で更新
• dp[ i + 1 ][ j ] を dp[ i ][ j ] で更新

の二通りです。
ハンバーの種類は最大で 100 種類なので十分間に合います。計算が終わった後、dp[ 100 ][ i ] * i の最大値が答えです。

コード

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

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

const int INF = INT_MAX / 2;

class AlienAndHamburgers
{
public:
	int getNumber( vector <int> type, vector <int> taste )
	{
		const int N = type.size();

		VVI type2taste( 100 );
		REP( i, 0, N )
		{
			type2taste[ type[i] - 1 ].PB( taste[i] );
		}
		FOR( ts, type2taste )
		{
			sort( ALL( ts ), greater<int>() );
		}

		VVI dp( 101, VI( 102, -INF ) );
		dp[0][0] = 0;

		REP( i, 0, 100 )
		{
			REP( j, 0, 101 )
			{
				{ // eat
					int s = 0;
					FOR( t, type2taste[i] )
					{
						s += t;
						dp[ i + 1 ][ j + 1 ] = max( dp[ i + 1 ][ j + 1 ], dp[i][j] + s );
					}
				}
				{ // not eat
					dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] );
				}
			}
		}

		LL res = -INF;
		REP( i, 0, 101 )
		{
			res = max( res, (LL)i * dp.back()[i] );
		}
		return res;
	}
};