DPまとめコンテスト L - Deque

L - Deque

概要

数列が与えられ、二人のプレイヤーが交互に数列から数を取り除いてゆき、取り除いた数の得点を得るゲームを行う。
先手の得点を、後手の得点をとするとき、先手はを最大化、後手はを最小化しようとする。
二人のプレイヤーが最適に行動したときのを求めよ。

制約

方針

:
　からでゲームをするときのの最大値
　ただし、手番は「元のゲームを行ってその局面になった時の手番」とする
　（右半区間でゲームの得点をメモする）

DPの推移は次の通り。

• 、ただし符号は実際のゲームで残り１枚の時の手番が先手ならプラス、後手ならマイナス
• での得点を求めたい場合、「からをとるケース」と、「からをとるケース」の最適な方を選べばよい

感想

下記提出を参考にしました。
Submission #3940341 - Educational DP Contest / DP まとめコンテスト

解答

Submission #3974769 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	ll a[n];
	rep(i, n) cin >> a[i];
 
	ll dp[n+1][n+1];
	rep(i, n+1) rep(j, n+1) dp[i][j] = 0;
	// dp[i][j] :
	//  ai+1からajでゲームをするときのX-Yの最大値
	//  ただし、手番は「元のゲームを行ってその局面になった時の手番」とする
 
	for(int len = 1; len <= n; len++){
		for(int l = 0; l < n - len + 1; l++){
			int r = l + len;
			if((n - len) % 2 == 0){
				dp[l][r] = max(dp[l+1][r] + a[l], dp[l][r-1] + a[r-1]);
			}else{
				dp[l][r] = min(dp[l+1][r] - a[l], dp[l][r-1] - a[r-1]);
			}
		}
	}
 
	cout << dp[0][n] << endl;
}