Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alternately by selecting a number from either the left or the right end of the sequence. That number is then deleted from the board, and its value is added to the score of the player who selected it. A player wins if his sum is greater than his opponents.

Write a program that implements the optimal strategy. The optimal strategy yields maximum points when playing against the "best possible" opponent. Your program must further implement an optimal strategy for player 2.

PROGRAM NAME: game1

INPUT FORMAT

SAMPLE INPUT (file game1.in)

6
4 7 2 9
5 2

OUTPUT FORMAT

SAMPLE OUTPUT (file game1.out)

18 11

题意：
给出一个序列，两个玩家，每个玩家每次只能从序列两端任取一数，求第一个玩家能取到的数之和（分数）的最大值，剩下的为玩家2的分数。

代码：

/*
LANG: C
TASK: game1
*/
#include<stdio.h>
#define maxn 201
int n, ori, ans, ans2;
//F[i][j] 是从第i个序列到第j个序列中，一个玩家能取到的最大值。
int F[maxn][maxn], num[maxn];
int max(int a, int b)
{
    return a > b ? a : b;
}
int get_S(int a, int b)//求从i到j的序列中元素之和
{
    int p = 0, i;
    for (i = a; i <= b; i++)
    {
        p += num[i];
    }
    return p;
}
int get_F(int i, int j)
{
    if (F[i+1][j] == 0)//如果F[i+1][j]还没求过，则求F[i+1][j];
    {
        F[i+1][j] = get_F(i+1, j);
    }
    if (F[i][j-1] == 0)//如果F[i][j+1]还没求过，则求F[i][j+1];
    {
        F[i][j-1] = get_F(i, j-1);
    }
    //1.如果first取num[i], 则second取F[i+1][j]，然后first取get_S(i + 1, j) - F[i+1][j]
        //不是first取num[i], 在去F[i+1][j]，因为F[i+1][j]中接下来有F[i+2][j] 或 F[i+1][j-1]被second取走。
    //2.同1，然后取1和2的较大值
    return max(num[i] + get_S(i + 1, j) - F[i+1][j], num[j] + get_S(i, j - 1) - F[i][j-1]);
}
void init()
{
    int i;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
        F[i][i] = num[i];
    }
}
void print()
{
    printf("%d %d\n", ans, ans2);
}
int main()
{
    freopen("game1.in", "r", stdin), freopen("game1.out", "w", stdout);
    init();
    ans = get_F(1, n);
    ans2 = get_S(1, n) - ans;
    print();
    fclose(stdin), fclose(stdout);
    return 0;
}