本文正體字版由OpenCC轉換

博弈問題，可以使用動態規劃求解。 狀態定義：用F[i][j]表示第一個玩家先取時，在第i到第j的子序列中能拿到的最高分；用S[i][j]表示第i到第j的子序列中所有數字的和；用num[i]表示第1到第n的序列中第i個數。

邊界條件：F[i][i]=num[i]

狀態轉移方程： F[i][j]=max{num[i]+S[i+1][j]-F[i+1][j],num[j]+S[i][j-1]-F[i][j-1]}

結果 p1=F[1][n]; p2=S[1][n]-F[1][n];

解析： num[i]+S[i+1][j]-F[i+1][j]表示的是，p1拿第i到第j最左邊的數，然後輪到p2在第i+1到第j的序列中先取，會剩下S[i+1][j]-F[i+1][j]，這些歸p1。

USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: game1 LANG: C++

Compiling… Compile: OK

Executing… Test 1: TEST OK [0.000 secs, 3000 KB] Test 2: TEST OK [0.011 secs, 3004 KB] Test 3: TEST OK [0.000 secs, 3000 KB] Test 4: TEST OK [0.000 secs, 3000 KB] Test 5: TEST OK [0.000 secs, 3000 KB] Test 6: TEST OK [0.022 secs, 3000 KB] Test 7: TEST OK [0.000 secs, 3000 KB] Test 8: TEST OK [0.011 secs, 3000 KB] Test 9: TEST OK [0.011 secs, 3004 KB] Test 10: TEST OK [0.000 secs, 3004 KB] Test 11: TEST OK [0.011 secs, 3004 KB] Test 12: TEST OK [0.000 secs, 3000 KB] Test 13: TEST OK [0.011 secs, 3000 KB] Test 14: TEST OK [0.000 secs, 3000 KB] Test 15: TEST OK [0.000 secs, 3004 KB] Test 16: TEST OK [0.011 secs, 3004 KB]

All tests OK.

YOUR PROGRAM (‘game1’) WORKED FIRST TIME! That’s fantastic – and a rare thing. Please accept these special automated congratulations.

/*
ID: cmykrgb1
PROG: game1
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAXN 201
using namespace std;
ifstream fi("game1.in");
ofstream fo("game1.out");
long n,ori,ans,ans2;
long F[MAXN][MAXN],num[MAXN];

inline long max(long a,long b)
{
	return a>b?a:b;
}

long get_S(long a,long b)
{
	long p=0;
	for (long i=a;i<=b;i++)
		p+=num[i];
	return p;
}

long get_F(long i,long j)
{
	if (F[i+1][j]==ori)
		F[i+1][j]=get_F(i+1,j);
	if (F[i][j-1]==ori)
		F[i][j-1]=get_F(i,j-1);
	return max(num[i]+get_S(i+1,j)-F[i+1][j],num[j]+get_S(i,j-1)-F[i][j-1]);
}

void init()
{
	long i;
	fi >> n;
	memset(F,0xF,sizeof(F));
	ori=F[0][0];
	for (i=1;i<=n;i++)
	{
		fi >> num[i];
		F[i][i]=num[i];
	}
}

void print()
{
	fo << ans << ' ' << ans2 << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	ans=get_F(1,n);
	ans2=get_S(1,n)-ans;
	print();
	return 0;
}

上次修改時間 2017-02-03