[BAE/<JOON> 문제풀이] 11062. 카드게임

www.acmicpc.net/problem/11062

11062번: 카드 게임

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

pair<int, int> dp[2][1001][1001];
vector<int> arr;

pair<int, int> comp2(int s, int e, int turn) {
	pair<int, int>& ret = dp[turn][s][e];
	if (ret != pair<int, int>{ -1, -1 }) {
		return ret;
	}
	if (s == e) {
		if (turn == 0) {
			return ret = pair<int, int>{ arr[s], 0 };
		}
		else {
			return ret = pair<int, int>{ 0, arr[s] };
		}
	}
	pair<int, int> p1, p2;
	if (turn == 0) {
		p1 = comp2(s + 1, e, 1 - turn);
		p2 = comp2(s, e - 1, 1 - turn);
		ret = p1.first + arr[s] > p2.first + arr[e] ?
			pair<int, int> { p1.first + arr[s], p1.second } :
			pair<int, int>{ p2.first + arr[e], p2.second };
		return ret;
	}
	else {
		p1 = comp2(s + 1, e, 1 - turn);
		p2 = comp2(s, e - 1, 1 - turn);
		ret = p1.second + arr[s] > p2.second + arr[e] ?
			pair<int, int> { p1.first, p1.second + arr[s] } :
			pair<int, int>{ p2.first, p2.second + arr[e] };
		return ret;
	}
}

int main()
{
	int tc;
	cin >> tc;
	while (tc--) {
		int n;
		cin >> n;
		arr.resize(n + 1, 0);
		memset(dp, -1, sizeof(dp));
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}
		auto res = comp2(1, n, 0);
		cout << res.first << endl;
	}

	return 0;
}