usaco_3_3_5_game1.cpp

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

/*
ID: wangyuc2
PROB:game1
LANG: C++
*/
/*
从终盘往前推，每次选择左右两端最大的加给当前的玩家，知道扩展到开始。
枚举终盘所在位置，选择每次玩家1得分最高的一次，输出结果。
贪心+枚举……
*/
#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 main()
{
	int bd[MAXV];
	int best[MAXV][2];
	int i,n,j,l,r,m,s1,s2;
	bool p2;
	memset(best,0,sizeof(best));
	cin>>n;
	bd[0]=0;
	bd[n+1]=0;
	m=0;
	for(i=1;i<=n;i++) cin>>bd[i];
	for(i=1;i<=n;i++){
		l=i-1;
		r=i+1;
	
		if(n%2==0) {best[i][1]+=bd[i]; p2=false;}
		else {best[i][0]+=bd[i]; p2=true;}
		s1=0;s2=0;
		while(l!=0 || r!=n+1){
			if(p2){
				if(bd[l]>=bd[r]){
					best[i][1]+=bd[l];
					l--;
				}
				else { best[i][1]+=bd[r]; r++;}
				p2=!p2;
			}
			else{
				if(bd[l]>bd[r]){
					best[i][0]+=bd[l];
					l--;
				}
				else { best[i][0]+=bd[r]; r++;}
				p2=!p2;
			}
		}
		if(best[i][0]>m) {m=best[i][0]; j=i;}
		
	}
//	for(i=0;i<n;i++) cout<<best[i][0]<<' '<<best[i][1]<<endl;
	fout<<best[j][0]<<' '<<best[j][1]<<endl;
	return 0;
}