TopCoder SRM 602, Division 2, Level 2 : PilingRectsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12928&rd=15820

概要

　N 個の長方形があり、i 番の長方形の高さは Y[ i ] 、幅は X[ i ] である。この内いくつかを選んで机の上に置く。このとき、長方形の辺はいずれかの座標軸に並行でなければならない。配置が終わった後、配置した全ての長方形によって被覆されている部分の面積を計算する。
　整数 limit が与えられる。例の面積が limit 以上になるように長方形を配置するとき、最大でいくつの長方形を配置することができるか求めよ。一つも配置できない場合は -1 で示せ。

解法

　まず前提として、配置する長方形とその向きが決まったとき、（例えば）左下の角を揃えて置くようにすると積集合部分の面積を最大にできます。
　それぞれの長方形について、どのようにするかを決めていくとします。そうすると、ある一つの長方形について取れる選択は三つで、

• 配置しない
• そのままの向きで置く
• 90 度回転させて置く

のいずれかです。左下を揃えることにしているので、このときの積集合部分は今までに置かれた長方形の内で最小の高さと最小の幅によって張られる領域です。積集合部分の高さと幅が等しいなら置かれている長方形の数は多い方が良いと考えると、次のような DP を考えることができます。

• dp[ i 個考慮した ][ 高さが j ][ 幅が k ] := 置いた数の最大

　dp[ i ][ j ][ k ] からの状態遷移は次の三通りです。

• dp[ i + 1 ][ j ][ k ] を dp[ i ][ j ][ k ] で更新（置かない）
• dp[ i + 1 ][ min( j, Y[ i ] ) ][ min( k, X[ i ] ) ] を dp[ i ][ j ][ k ] + 1 で更新（そのまま置く）
• dp[ i + 1 ][ min( j, X[ i ] ) ][ min( k, Y[ i ] ) ] を dp[ i ][ j ][ k ] + 1 で更新（回転して置く）

　この計算が終わったあと、dp[ N ][ j ][ k ] ( ただし limit <= j * k ) の最大値が答えになっています。

コード

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 / 4;

class PilingRectsDiv2
{
public:
	int getmax( vector <int> X, vector <int> Y, int limit )
	{
		const int N = X.size();

		vector<VVI> dp( N + 1, VVI( 201, VI( 201, -INF ) ) );
		dp[0][200][200] = 0;

		REP( i, 0, N )
		{
			REP( j, 0, 201 )
			{
				REP( k, 0, 201 )
				{
					{ // 置かない
						dp[ i + 1 ][j][k] = max( dp[ i + 1 ][j][k], dp[i][j][k] );
					}
					{ // そのまま
						const int nj = min( j, X[i] );
						const int nk = min( k, Y[i] );
						dp[ i + 1 ][ nj ][ nk ] = max( dp[ i + 1 ][ nj ][ nk ], dp[i][j][k] + 1 );
					}
					{ // 回転
						const int nj = min( j, Y[i] );
						const int nk = min( k, X[i] );
						dp[ i + 1 ][ nj ][ nk ] = max( dp[ i + 1 ][ nj ][ nk ], dp[i][j][k] + 1 );
					}
				}
			}
		}

		int res = 0;
		REP( j, 0, 201 )
		{
			REP( k, 0, 201 )
			{
				if ( limit <= j * k && dp[N][j][k] )
				{
					res = max( res, dp[N][j][k] );
				}
			}
		}

		return res ? res : -1;
	}
};