USACO Section 3.3 A Game pascal代码,最好带解释。

发布网友发布时间：2024-10-01 15:11

共1个回答

热心网友时间：2024-10-17 23:29

您好：这是个双人博弈问题。博弈的最优策略是使对方获利最小的情况下使自己获利最大（“最坏最好”），在搜索中著名的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;
}

如楼主急pascal代码，采纳后通知即可

热心网友时间：2024-10-17 23:36