usaco_3_3_5_game1.cpp

usaco自己做的1到5章的代码

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