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;
}