Typical DP Contest B ゲーム

問題

http://tdpc.contest.atcoder.jp/tasks/tdpc_game

方針

すぬけ君は得られる得点を最大化しようとして、すめけ君はすぬけ君の得られる得点を最小化しようとする。

min-max探索をメモ化すればいい。

ソースコード

int A, B, a[1000], b[1000], dp[1001][1001];

void chmax(int &a, int b){
	if(a == -inf || a < b) a = b;
}
int rec(int i, int j, int k){
	int &res = dp[i][j];
	if(res != -inf) return res;
	
	if(k == 1){
		res = inf;
		if(i < A) res = min(res, rec(i+1, j, 0));
		if(j < B) res = min(res, rec(i, j+1, 0));
	}
	else{
		if(i < A) res = max(res, rec(i+1, j, 1) + a[i]);
		if(j < B) res = max(res, rec(i, j+1, 1) + b[j]);
	}
	return res;
}

int main(){
	cin >> A >> B;
	rep(i, A) cin >> a[i];
	rep(i, B) cin >> b[i];
	
	rep(i, A+1) rep(j, B+1) dp[i][j] = -inf;
	dp[A][B] = 0;
	cout << rec(0, 0, 0) << endl;
	return 0;
}