USACO Training Section 3.3 A Game

英文原题 

有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。

编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为两位玩家执行最优策略。
sample input ：
6
4 7 2 9 5 2
sample output :
18 11
解释：
下面是按最优策略取值的步骤：
A 2
B 5
A 9
B 2
A 7
B 4
这是个双人博弈问题。博弈的最优策略是使对方获利最小的情况下使自己获利最大（“最坏最好”），在搜索中著名的alpha-beta搜索就是针对这种情况：这种博弈假设对手是总是采用最优策略（也就是：遇到“最坏”的对手），而在这种情况下，选择一个行动使得对手的获利最小，即为自身的最优策略。从而，很容易的得到此题的动态规划方程：
设sum(s,t)为区间s,t中的数字之和，gain(s,t)为按最优策略能获得的最大得分，那么，有两种数字的方式，
1.取s，则给对手余下区间(s+1,t)，对手的收益将是gain(s+1,t);
2.或者取t，则给对手留下区间(s,t-1)，对手的收益将是gain(s,t-1);
无论如何，自身得分是sum(s,t)-对手得分，从而：
gain(s,t)=sum(s,t)-min{gain(s+1,t),gain(s,t-1)}.
程序极为简单。

不过此题引发了我对搜索与DP之间的关系的思考。在搜索注意了重复状态判断与回溯记录结果之后，可进行剪枝，应当比DP更快。只是在算法设计和编程上要复杂很多。之前一直困扰我的这个问题，似乎快有了答案。

/*
ID: blackco3
TASK: game1
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
const int _max_len_(100) ;
int n_size, val[_max_len_], sum[_max_len_], gain[_max_len_][_max_len_] ;

int main() {
	freopen("game1.in", "r", stdin) ;
	freopen("game1.out", "w", stdout) ;
	cin >> n_size ;
	for( int i=0; i<n_size; i++ )
		cin >> val[i] , sum[i] = ( i ? sum[i-1] : 0 ) + val[i] , gain[i][i]=val[i];
	for( int s=n_size-1; s>=0; s-- )
		for( int t=s+1; t<n_size; t++ )
			gain[s][t] = sum[t] - (s?sum[s-1]:0) - min( gain[s][t-1], gain[s+1][t] );
	cout << gain[0][n_size-1] << " " << sum[n_size-1]-gain[0][n_size-1] << endl ;		
	return 0;
}