USACO Section3.3 game1

Problem Summary

Two players play a game with a sequence of N positive integers laid onto a 1*N game board. Player 1 starts the game and they move alternately by selecting a number from either the left or the right end of the board. The selected number is then deleted, and its value is added to the score of the player who selected it. Whoever has the greater sum in the end wins.
Write a program that implements the optimal strategy for player 2. The optimal strategy yields maximum points when playing against the “best possible” opponent.

Solution

We can use dynamic programming to compute the best scores.
Define f[i][j] to be the highest score we can get by going first with the sequence from i to j.
Then the player can choose data[i] or data[j],and leave the rest to his opponent. So we can write :

f[i][j] = max(data[i]+sum[i+1][j]-f[i+1][j],data[j]+sum[i][j-1]-f[i][j-1]), 1<=i<j<=N
f[i][i] = data[i], 1<=i<=N

Code

#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
#include <cmath>

using namespace std;

const int maxn = 102;

int n,d[maxn];
int sum[maxn][maxn],f[maxn][maxn];

int main()
{
	fstream fin("game1.in",ios::in);
	fstream fout("game1.out",ios::out);

	fin>>n;
	for(int i=1;i<=n;i++)
	{
		fin>>d[i];
		f[i][i]=sum[i][i]=d[i];
	}

	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			sum[i][j]=sum[i][j-1]+d[j];

	for(int len=2;len<=n;len++)
		for(int i=1;i<=n-len+1;i++)
		{
			int j=i+len-1;
			f[i][j]=max(d[i]+sum[i+1][j]-f[i+1][j],d[j]+sum[i][j-1]-f[i][j-1]);
		}

	fout<<f[1][n]<<" "<<sum[1][n]-f[1][n]<<endl;

	fin.close();
	fout.close();
	return 0;
}