游戏 A Game"/>
P2734 游戏 A Game
题目背景
有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上,游戏由玩家1开始,两人轮流从序列的任意一端取一个数,取数后该数字被去掉并累加到本玩家的得分中,当数取尽时,游戏结束。以最终得分多者为胜。
题目描述
编一个执行最优策略的程序,最优策略就是使玩家在与最好的对手对弈时,能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。
输入输出格式
输入格式:
第一行: 正整数N, 表示序列中正整数的个数。
第二行至末尾: 用空格分隔的N个正整数(大小为1-200)。
输出格式:
只有一行,用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。
输入输出样例
输入样例#1: 复制6 4 7 2 9 5 2输出样例#1: 复制
18 11
说明
题目翻译来自NOCOW。
USACO Training Section 3.3
//博弈论 好题(nan)好题(nan) //dp[i][j]表示先手在i->j区间内能取的的最大得分 //dp[i][j]=max(sum[j]-sum[i-1]-dp[i+1][j],sum[j]-sum[i-1]-dp[i][j-1]);//dp[i+1][j]表示我们取了a[i],然后我们就变成了后手。而我们的对手成了先手。 //我们的对手是很聪明的,所以他会取最优的。 //那在我们这次操作之后直到游戏结束,他取得的数的和就一定是dp[i+1][j] //剩下来的数的和就是sum[j]-sum[i]-dp[i+1][j] //当我们取a[j]时同理。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int N=105;int n; int a[N],sum[N]; int dp[N][N];int main() {scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",a+i);dp[i][i]=a[i];sum[i]=sum[i-1]+a[i];}for(int k=2;k<=n;++k){for(int i=1;i<=n-k+1;++i){int j=i+k-1;dp[i][j]=max(sum[j]-sum[i-1]-dp[i+1][j],sum[j]-sum[i-1]-dp[i][j-1]);}}printf("%d %d",dp[1][n],sum[n]-dp[1][n]);return 0; }
转载于:.html
更多推荐
P2734 游戏 A Game
发布评论