【题解】 P2734 [USACO3.3]游戏 A Game

(color{purple}{Link})

( ext{Solution:})

考虑区间([l,r])的最优解。显然它可以由([l+1,r])或([l,r-1])转移而来。至此出现区间(dp)模型。

因为这个是求双方最优解，显然对于一段区间([l,r])，如果对手选择最优解，那么剩下的也是我们的最优解。

于是直接记忆花搜索即可。复杂度(O(n^2).)

#include<bits/stdc++.h>
using namespace std;
int n,a[500],dp[101][101],sum[500],A;
int dfs(int l,int r){
	if(l==r)return dp[l][r]=a[l];
	if(~dp[l][r])return dp[l][r];
	int &F=dp[l][r];
	F=sum[r]-sum[l-1]-dfs(l,r-1);
	F=max(F,sum[r]-sum[l-1]-dfs(l+1,r));
	return F;
}
int main(){
	scanf("%d",&n);memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	A=dfs(1,n);
	printf("%d
",A);
	return 0;
}