学步园

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1231

题意:取数游戏是一个 2 人对策游戏。游戏开始时将 n 个数在棋盘上从左到右排成一行。甲乙双方轮流在这一行数的左右 2 端取数，直至全部取完 n 个数。每人所取得的数的总和为其得分值。最后双方得分多者获胜。游戏规定由甲方先取数。
★算法设计： 在甲乙双方都采用最优策略的前提下，计算甲方先取数时双方的最后得分。

解题思路：首先要明确2个人都采取最优的策略，既:
到A取，A希望自己取的这个数能使他的分数尽量高
到B取，B希望A取到的分数尽量低
于是可以很容易的得到一个3维的DP

opt[l][r][s]：s=0时表示甲面对（l,r）时甲得到的最优值，s=1表示乙面对（l,r）时甲得到的最优值，注意这里记录的都是甲的最优值。

#include<iostream>
#include<stdio.h>
#define N 105
using namespace std;
int a[N],opt[N][N][2],n;
int dfs(int l,int r,int s)//s=1表示后手面对当前局面我得到的最优值，
{
    if(l==r) return s?0:a[l];
    int &ret=opt[l][r][s];
    if(ret!=-1) return ret;
    int ta,tb;
    ta=dfs(l+1,r,s^1);
    tb=dfs(l,r-1,s^1);
    if(s==0) ret=max(a[l]+ta,a[r]+tb);
    else ret=min(ta,tb);
    return ret;
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        int s=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),s+=a[i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                opt[i][j][0]=opt[i][j][1]=-1;
        printf("%d %d\n",dfs(1,n,0),s-dfs(1,n,0));
    }
    return 0;
}