刷题记录:CF859C - Pie Rules [博弈论dp]

传送门:CF

题目描述:

有一个长度为nn的序列，Alice和Bob在玩游戏。Bob先手掌握决策权。
他们从左向右扫整个序列，在任意时刻，拥有决策权的人有如下两个选择：
将当前的数加到自己的得分中，并将决策权给对方，对方将获得下一个数的决策权
将当前的数加到对方的得分中，并将决策权保留给自己，自己将获得下一个数的决策权
假定他们都使用最优策略，求他们最后分别能获得多少分
输入:
3
141 592 653
输出:
653 733

一道博弈论dp的题目,写这道题目的原由是下午VP比赛时碰到了一道博弈论dp的题目,但是当时的自己想出了dp方程,但是脑子里一直想的是正推,一直AC不过去,赛后查了一下发现是博弈论dp的题目

对于博弈论dp的题目,我们大都是从后面的决策倒推到前面来的.为什么呢,因为博弈论的问题,我们在之前所选择的决策会对后面的选择产生影响,这就违背了我们的dp的无后效性,但是当我们倒推的时候,我们发现我们的决策就是无后效性的!!

对于这道题来说,假设我们选择正推,那么我们的$dp[i][person]$方程应该是$porson$选择完前$i$个数字的最大得分,但是对于我们当前第$i$个数字的选择,我们会发现,这个数字影响到了我们后面的决策!!所以这个dp方程是错误的.我们此时准备倒推,我们将我们的dp方程改一下,将$dp[i][person]$改成当前person选完第i个数字之后Bob所总共能得到的最大和(请仔细理解这句话),此时我们会发现我们后面的数字的选择是不会影响到我们之前的决策的,所以此时我们就可以进行$dp$了.

我们将person=1代表Bob,person=0代表Alice

此时的dp方程也不难想.对于第$i$个数字,如果当前决策权在Bob手中,有两种情况:
1.Bob选择要:那么此时的dp方程就是 $dp[i][1]=dp[i+1][0]+a[i]$ 决策权变换
2.Bob选择不要:那么此时dp方程就是 $dp[i][1]=dp[i+1][1]$ 决策权不变

当前决策权在Alice手上,也有两种情况:
1.Alice选择要,那么 $dp[i][0]=dp[i+1][1]$ 决策权变换,但是数字和没有增加
2.Alice选择不要.那么 $dp[i][0]=dp[i+1][0]+a[0]$ 决策权不变但是数字和增加

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int n;int a[maxn];int dp[maxn][2];
int solve(int step,int person) {
	if(step>n) return 0;
	if(dp[step][person]!=-1) return dp[step][person];
	if(person==0) {
		int temp1=solve(step+1,1)+a[step];
		int temp2=solve(step+1,0);
		return dp[step][person]=max(temp1,temp2);
	}else {
		int temp2=solve(step+1,1)+a[step];
		int temp1=solve(step+1,0);
		return dp[step][person]=min(temp1,temp2);
	}
}
int main() {
	int sum=0;
	memset(dp,-1,sizeof(dp));
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();sum+=a[i];
	} 
	solve(1,0);
	cout<<sum-dp[1][0]<<" "<<dp[1][0]<<endl;
	return 0;
}