题面
题目背景
有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上，游戏由玩家1开始，两人轮流从序列的任意一端取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
题目描述
编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。
输入输出格式
输入格式：
第一行: 正整数N, 表示序列中正整数的个数。
第二行至末尾: 用空格分隔的N个正整数（大小为1-200）。
输出格式：
只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。
输入输出样例
输入样例#1：
6
4 7 2 9 5 2
输出样例#1：
18 11
说明
题目翻译来自NOCOW。
USACO Training Section 3.3
题解
首先它看起来像是一道博弈论，但是仔细分析，就会发现它不过是要求第二个人取数的和值最大
所以是一道区间取数的DP（没错我瞄了眼题解）
然后开始做题
蒟蒻的我还是naive的很，然后脑子一热就写下了以下的状态转移
\( dp[i][j] = max(dp[i+1][j]+a[i],dp[i][j-1]+a[j] ) \)
简直脑残（雾）
因为这是两个人取数，不是一个人拿数字，所以理所当然的就WA了
然后我们考虑到，在序列中，一个人拿完之后，另一个人会拿到其他的所有
所以让\( dp[i][j] \)表示先手在区间\( \left [ i,j \right ] \)的最大值
状态转移方程就变成了
\( dp[i][j]=max(sum[i][j]-dp[i+1][j],sum[i][j]-dp[i][j-1]) \)
然后前缀和随便搞一搞
A了QwQ
被这种题吊打，果然我还是太蒟蒻了
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[][],a[],sum[],n;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),sum[i]+=sum[i-]+a[i];
for(int i=;i<=n;i++)
dp[i][i]=a[i];
for(int l=;l<=n;l++)
for(int i=;i+l-<=n;i++)
dp[i][i+l-]=sum[i+l-]-sum[i-]-min(dp[i+][i+l-],dp[i][i+l-]);
printf("%d %d",dp[][n],sum[n]-dp[][n]);
return ;
}