Home > Old Blog Posts > USACO 3.3.5 A Game

USACO 3.3.5 A Game


这是一道博弈问题,似乎也是USACO唯一的一道博弈问题,当时我一看到这题就傻眼了,现在看来其实也很简单
由于博弈者都执行最优策略,显然这道题可以用动态规划来解决。设f[i][j]为序列的第i项到第j项,先取者能获得的最大得分,又设sum[i][j]为序列第i项到第j项的和,则
f[i][j]=sum[i][j]-min(f[i][j-1],f[i+1][j])
为了理解这个方程,可想象先行者需决策从左边取还是从右边取,为了使自己最大,显然要使对手最小
边界条件:f[i][i]=a[i]

/*
ID: dementr1
PROG: game1
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("game1.in");
ofstream fout("game1.out");
int a[100]={},N;
void init()
{
	int i;
	fin>>N;
	for(i=0;i>a[i];
}
void work()
{
	int sum[100][100]={},f[100][100]={};
	int i,j,step;
	for(i=0;i<N;i++)
	{
		sum[i][i]=a[i];
		for(j=i+1;j<N;j++)
			sum[i][j]=sum[i][j-1]+a[j];
	}
	for(step=0;step<N;step++)
		for(i=0;i=i) tmp=f[i][i+step-1];
			if(i+1<=i+step&&f[i+1][i+step]<tmp) tmp=f[i+1][i+step];
			f[i][i+step]=sum[i][i+step]-tmp;
		}
	fout<<f[0][N-1]<<" "<<sum[0][N-1]-f[0][N-1]<<endl;
}
int main()
{
	init();
	work();
	return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: