题解——洛谷P2734 游戏A Game 题解(区间DP)

时间:2023-12-14 17:41:14

题面

题目背景

有如下一个双人游戏: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

题解

首先它看起来像是一道博弈论,但是仔细分析,就会发现它不过是要求第二个人取数的和值最大

所以是一道区间取数的DP(没错我瞄了眼题解)

然后开始做题

蒟蒻的我还是naive的很,然后脑子一热就写下了以下的状态转移

\( dp[i][j] = max(dp[i+1][j]+a[i],dp[i][j-1]+a[j] ) \)

简直脑残(雾)

因为这是两个人取数,不是一个人拿数字,所以理所当然的就WA了

然后我们考虑到,在序列中,一个人拿完之后,另一个人会拿到其他的所有

所以让\( dp[i][j] \)表示先手在区间\( \left [ i,j \right ] \)的最大值

状态转移方程就变成了

\( dp[i][j]=max(sum[i][j]-dp[i+1][j],sum[i][j]-dp[i][j-1]) \)

然后前缀和随便搞一搞

A了QwQ

被这种题吊打,果然我还是太蒟蒻了

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[][],a[],sum[],n;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),sum[i]+=sum[i-]+a[i];
for(int i=;i<=n;i++)
dp[i][i]=a[i];
for(int l=;l<=n;l++)
for(int i=;i+l-<=n;i++)
dp[i][i+l-]=sum[i+l-]-sum[i-]-min(dp[i+][i+l-],dp[i][i+l-]);
printf("%d %d",dp[][n],sum[n]-dp[][n]);
return ;
}