AtCoder Beginner Contest #008, D : 金塊ゲーム

問題文

http://abc008.contest.atcoder.jp/tasks/abc008_4

問題概要

　説明しづらいので本家問題文参照で＞＜

解法

　ある装置を使用したときに何が起こるかを詳細に考えます。装置を使用したとき、その装置は空セルに当たるまでクレーンを伸ばします。また（同じことですが）、装置は空セルの向こうにある金塊を回収することはできません。ということは、その装置を使用すると盤面全体が 4 つに分割され、以降関係が無くなります。分割された盤面による問題は最初の問題と同じ形式の部分問題となります。また、各部分問題は互いに影響を及ぼさないので独立に計算することができます。更に、ある部分問題の最適解は一意に定まります。部分問題がよい性質をもつので、動的計画法を適用できそうです。
　ということで、ある盤面上の矩形領域に対する最適解をメモするメモ化再帰を考えます。このとき、その部分問題から取れる選択肢は、領域内にあるいずれかの装置を作動させることです。作動される装置をすべて試して、最も良かった結果をその領域に対する最適解としてメモすると DP にできます。
　ここで問題になるのは計算量ですが、実は部分問題として現れる矩形領はあまり多くありません。というのも、盤面の分割が起こる座標は装置が存在する座標のみであることによります。部分問題の矩形領域の X 座標の両端の組み合わせは 、Y 座標の両端の組み合わせも です。従って部分問題として現れる矩形領域の総数は であり、必要な情報だけを保持するようにすればこれがそのまま空間計算量となります。また部分問題毎の選択肢は 個なので、時間計算量は です。まだ余裕があるので、以下のコードでは横着してメモ化に std::map を使っています。

コード

using LL = long long;
using VI = vector<int>;
using VPII = vector< pair<int,int> >;

template < typename T > inline T fromString( const string &s ){ T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

LL rec( const VPII &ps, const int x1, const int x2, const int y1, const int y2 )
{
	using key_t = tuple<int,int,int,int>;
	static map< key_t, LL > dp;
	const key_t key( x1, x2, y1, y2 );

	if ( EXIST( dp, key ) )
	{
		return dp[ key ];
	}

	LL res = 0;
	FOR( p, ps )
	{
		const array<int,4> x1s = { p.fst + 1, x1, x1, p.fst + 1 };
		const array<int,4> x2s = { x2, p.fst - 1, p.fst - 1, x2 };
		const array<int,4> y1s = { p.snd + 1, p.snd + 1, y1, y1 };
		const array<int,4> y2s = { y2, y2, p.snd - 1, p.snd - 1 };

		if ( x1 <= p.fst && p.fst <= x2 && y1 <= p.snd && p.snd <= y2 )
		{
			LL tmp = x2 - x1 + y2 - y1 + 1;
			REP( i, 0, 4 )
			{
				tmp += rec( ps, x1s[i], x2s[i], y1s[i], y2s[i] );
			}
			res = max( res, tmp );
		}
	}

	return dp[ key ] = res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int w, h;
	cin >> w >> h;

	int n;
	cin >> n;

	VPII ps( n );
	FOR( p, ps )
	{
		cin >> p.fst >> p.snd;
	}

	cout << rec( ps, 1, w, 1, h ) << endl;

	return 0;
}