有如下一个双人游戏:N个正整数的序列放在一个游戏平台上,两人轮流从序列的两端取数,每次有数字被一个玩家取走后,这个数字被从序列中去掉并累加到取走该数的玩家的得分中,当数取尽时,游戏结束。以最终得分多者为胜。
编一个执行最优策略的程序,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为两位玩家执行最优策略。
行包括一个正整数N(2≤N≤100), 表示序列中正整数的个数。输入第2行包含用空格分隔的N个正整数(1≤所有正整数≤200)。
只有一行,用空格分隔的两个整数: 依次为先取数玩家和后取数玩家的最终得分。
样例1
输入:
6
4 7 2 9 5 2
输出:
18 11
想找简单的博弈论题目做做,就找了这道。
我们 设 d[i][j]代表以 i 为起点,有j 个数时,先取者所能得到的最大分数,对于一段数字,先取者可以拿左右两端中的任意一个,由于两个玩家始终选择当前最佳策略,故可以得到状态转移方程 d[i][j] = max{s[i~i+j]- d[i+1][j-1],s[i~i+j]-d[i][j-1]}。S[i~i+j]代表从i到i+j-1这j 个数之和。
- #include <stdio.h>
- #define N 105
- #define max(a,b) ((a)>(b)?(a):(b))
- int a[N],s[N],d[N][N];
- int main(){
- int n,i,j;
- scanf("%d",&n);
- for(i=1;i<=n;i++){
- scanf("%d",&a[i]);
- s[i]=s[i-1]+a[i];//保存前n项和,利用差来得到范围和
- }
- for(i=n-1;i>0;i--){
- d[i][2]=max(a[i],a[i+1]);
- for(j=3;i+j<=n+1;j++)
- d[i][j]=max(s[i+j-1]-s[i-1]-d[i+1][j-1],
- s[i+j-1]-s[i-1]-d[i][j-1]);
- }
- printf("%d %d",d[1][n],s[n]-d[1][n]);
- }
好久没做题了,是时候准备开学了。