A Game
IOI'96 - Day 1 
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
Line 1:
N, the size of the board
Line 2-etc:
N integers in the range (1..200) that are the contents of the game board, from left to right
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
Two space-separated integers on a line: the score of Player 1 followed by the score of Player 2.
SAMPLE OUTPUT (file game1.out)
18 11

USER: wang yucao [wangyuc2]
TASK: game1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2856 KB]
   Test 2: TEST OK [0.000 secs, 2860 KB]
   Test 3: TEST OK [0.000 secs, 2856 KB]
   Test 4: TEST OK [0.000 secs, 2848 KB]
   Test 5: TEST OK [0.011 secs, 2848 KB]
   Test 6: TEST OK [0.011 secs, 2856 KB]
   Test 7: TEST OK [0.000 secs, 2852 KB]
   Test 8: TEST OK [0.000 secs, 2848 KB]
   Test 9: TEST OK [0.011 secs, 2856 KB]
   Test 10: TEST OK [0.000 secs, 2856 KB]
   Test 11: TEST OK [0.000 secs, 2852 KB]
   Test 12: TEST OK [0.000 secs, 2848 KB]
   Test 13: TEST OK [0.000 secs, 2856 KB]
   Test 14: TEST OK [0.000 secs, 2848 KB]
   Test 15: TEST OK [0.022 secs, 2856 KB]
   Test 16: TEST OK [0.011 secs, 2852 KB]

All tests OK.
Your program ('game1') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!
 
/*
ID: wangyuc2
PROB:game1
LANG: C++
*/
/*
动规题……
Record1[i][j]代表第一个人，从　i　到　j　的取石子能得到的最大和，同理，用Record2[i][j]表示第二个人，题目要求第二个人的最优方案，那个可列方程如下：
Record1[i][j] = Max(Record2[i+1][j] + Array[i],Record2[i][j-1]+Array[j]),
Record2[i][j] = Sum[j] - Sum[i-1] - Record1[i][j];
Sum[i]代表前Ｉ个石子的数量和，这样，这道题就搞定了，注意，由于每一个人先选，那么Record1[][]数组对角线上的元素都应该为Record1[k][k] = Array[k]，而Record2[k][k] =0;这样就可以了，为了避免数组越界及特殊情况，这样，我们存储时要从１开始，这样更加简洁．
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#define MAXV 202
#define MAXE 1000
#define cin fin
using namespace std;
ifstream fin("game1.in");
ofstream fout("game1.out");
int Max(int x,int y)
{
     return x>y?x:y;
}     
int main()
{
 int i,j,k;
 int Sum[105]={0};
 int Array[105]={0};
 int Record1[105][105]={0};
 int Record2[105][105]={0};
 int N;
     cin>>N;
     for(i=1;i<=N;i++)
     {
         cin>>Array[i];
         Sum[i] = Sum[i-1] + Array[i]; 
     }      
     for(k=1;k<=N;k++)
     {
         Record1[k][k] = Array[k];
         Record2[k][k] = 0;
     }     
     for(k=1;k<=N-1;k++)
     for(i=1;i<=N-k;i++)
     {
         j = k+i;
         Record1[i][j] = Max(Record2[i+1][j]+Array[i],Record2[i][j-1]+Array[j]);
         Record2[i][j] = Sum[j] - Sum[i-1] - Record1[i][j];
     }        
     fout<<Record1[1][N]<<" "<<Record2[1][N]<<endl;
 return 0;
}