AtCoder Beginner Contest #008 D- 金塊ゲーム

問題

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

感想

AtCoder Beginner Contest 008 解説
解説スライドを見ながら解きました。

#include <bits/stdc++.h>
using namespace std;

int w,h;
vector<int> x,y;
map<tuple<int,int,int,int>,int> memo;

int dfs(int l,int r,int u,int d){
	int res = 0;
	//枠内に回収機があるか
	bool f = false;
	tuple<int,int,int,int> tp = make_tuple(l,r,u,d);
	if(memo.count(tp) != 0)return memo[tp];

	for(int i=0;i<x.size();i++){
		int ret = 0;
		//枠内に回収機がある
		if(l <= x[i] && x[i] <= r && u <= y[i] && y[i] <= d){
			//回収機が枠の端以外にある時は、次の範囲を探索
			if(x[i] != l){
				if(y[i] != u)
					ret += dfs(l,x[i]-1,u,y[i]-1);
				if(y[i] != d)
					ret += dfs(l,x[i]-1,y[i]+1,d);
			}
			if(x[i] != r){
				if(y[i] != u)
					ret += dfs(x[i]+1,r,u,y[i]-1);
				if(y[i] != d)
					ret += dfs(x[i]+1,r,y[i]+1,d);
			}
			f = true;
		}
		res = max(res,ret);
	}
	//枠内に1個も回収機がない
	if(!f)return 0;
	//回収機があれば、(幅+高さ-1)個の金塊が回収できる
	return memo[tp] = res + (r-l+1)+(d-u+1)-1;
}

int main(void) {
	cin >> w >> h;
	int n;
	cin >> n;
	x.resize(n);y.resize(n);
	for(int i=0;i<n;i++){
		cin >> x[i] >> y[i];
	}
	cout << dfs(1,w,1,h) << endl;
	return 0;
}

当時は解説スライド見ても解けなかったし成長を僅かながら感じられた。