描述

取数对弈游戏问题：

取数游戏是一个 2 人对策游戏。游戏开始时将 n 个数在棋盘上从左到右排成一行。

甲乙双方轮流在这一行数的左右两端取数，直至全部取完 n 个数。每人所取得的数的总和为其得分值。

最后双方得分多者获胜。（游戏规定由甲方先取数。）

这里，甲乙双方都采用如下最优策略:
1)甲每次取都希望取到的这个数使自己得分最高
2)乙每次取都希望取到的这个数令甲的得分最低

请编程实现：在甲乙双方都采用最优策略的前提下，计算甲方先取数时双方的最后得分。

输入格式

对于每组输入数据，输入数据的第 1 行有 1 个正整数 n (1<=n<=100)，表示有 n 个数在棋盘上从左到右排成一行。
接下来的 n 个数表示在棋盘上依次排列的 n 个数。

输出格式

在甲乙双方都采用最优策略的前提下，输出计算出的双方的最后得分。甲方得分在前，乙方得分在后。

输入样例

6
4 7 2 9 5 2

输出样例

18 11

Hint

注意：此题“贪心法”是不能保证总可行且最优的，因为你不能只“关注眼前”，而“不管以后”。 ：）

1、前提和假设如下：
每次取数都只能从数列的头尾选择。甲乙双方都依最优策略来选择。（得分=所取的数之和）
sum(i,j)：表示a[i]到a[j]的元素之和，即sum(i,j) = a[i]+...+a[j]
p[i][j]：表示从a[i]到a[j]时，甲方先取数并在甲乙双方都采用最优策略的前提下时，甲方的最终得分。

注意：这个“甲乙双方都采用最优策略的前提”，其实是甲乙双方都尽量使自己的得分最大。
对甲方是使自己得分最高这个动机好理解，对乙方而言，使得甲方得分最低为下步策略，由于总分是一定的，其实也就是使乙方自己得分最大。
因此，虽然有甲乙2个人对弈，但他们动机是一致的。

2、分析如下：
当甲方取a[i]时，p[i][j] = sum(i,j) - p[i+1][j];
当甲方取a[j]时，p[i][j] = sum(i,j) - p[i][j-1];
甲方会取这两种情况较大的作为自己的选择。即sum(i,j) - min( p[i+1][j], p[i][j-1] )  

3、递归关系如下：
1）当j=i, p[i][j] = a[i];
2）当j>i, p[i][j] = sum(i,j) - min( p[i+1][j], p[i][j-1] )

4、题目所求为：
所求的甲方得分 = p[1][n]; 乙方得分 = sum - p[1][n]

5、例如：（左边界i，右边界j）
j=i     4   7   2   9   5   2
j=i+1     7   7   9   9   5
j=i+2       6   11  7   11
j=i+3         16  16  11
j=i+4           11  14
j=i+5             18

C++:

#include <iostream>
using namespace std;
 
int p[101][101];
 
int sum(int i, int j) {
    int sum_num = 0;
    for(int r = i; r <= j; r ++)
        sum_num += p[r][r];
    return sum_num;
}
 
int main()
{
    int n;
    int num[101];
    cin >> n;
    if(1 <= n && n <= 100) {
        for(int i = 1; i <= n; i ++) {
            cin >> num[i];
            p[i][i] = num[i];
        }
        for(int j = 2; j <=n; j ++) {
            for(int i =1; i <= n - j + 1; i ++) {
                int r = j + i - 1;
                p[i][r] = sum(i,r) - (p[i+1][r] < p[i][r-1] ? p[i+1][r] : p[i][r-1]);
            }
        }
        cout << p[1][n] << " " << sum(1,n) - p[1][n];
    }
    return 0;
}