【AcWing】蓝桥杯集训每日一题Day22|区间DP|博弈论|1388.游戏(C++)

1388.游戏

题目内容

玩家一和玩家二共同玩一个小游戏。
给定一个包含 N 个正整数的序列。
由玩家一开始，双方交替行动。
每次行动可以在数列的两端之中任选一个数字将其取走，并给自己增加相应数字的分数。（双方的初始分都是 0 分）
当所有数字都被取完时，游戏结束。
分更高的一方获胜。
请计算，如果双方都采取最优策略进行游戏，则游戏结束时，双方的得分各是多少。

输入格式

第一行包含整数 N。
后面若干行包含 N 个整数，表示这个序列。注意每行不一定恰好包含一个数。

输出格式

共一行，两个整数，分别表示玩家一和玩家二的最终得分。

数据范围

2≤N≤100,
数列中的数字的取值范围为 [1,200]。

输入样例：

6
4 7 2 9
5 2

输出样例：

18 11

题目解析

方案可能不唯一，分值是一样的，每个人都希望分值最高，都绝顶聪明，最终每个人的分值是唯一确定的
每一个选法得到的分值都是唯一确定的

N最大是100
序列中每一个数的最大值是200

博弈论

每一次有两种选择，是选左边的还是右边的呢，左边的就是$w_l$，右边的是$w_r$
要看条件和目标，目标是要分值尽可能高，由于所有数的总和是一定的
就是一个零和游戏
一方的分值越高，另一方的分值就越低
等价于，一方的分值减去另一方的分值最大，也就是差值最大

就是看选左边的话，差值A-B的最大值是多少，选右边的话，差值的最大值又是多少
两者要取一个max

• 比如选左边的话，剩下的问题就变成了从L+1到R的一个子问题，一个递归的问题
  该对手选了，对于对手来说，B-A差值最大是多少，可以求一下，如$S_{B-A}$
  我们减对方的分值就是$-S_{B-A}$再加上当前选择的分值L
  因此选左边的话，我们的分值就是$W_L-S_{B-A}$
• 同理，如果选右边的话，就变成了一个L到R-1的一个子问题
  最终的分值就是$W_R-S_{B-A}$
• 两者取一个最大值，就是当前的最大值

博弈论的核心

每次有多种选择，每次选完之后，一定要让最坏情况下最好，也就是我们选完之后，对方一定会选择对他来说最好的情况

在做的时候会发现会产生很多的子问题
可以用一个DP数组，把每一个子问题存起来，比如$S_{B-A}$
相当于对这个核心策略进行记忆化，就可以形成一个DP

f[L][R]
对于当前LR这个区间，先手分值减后手分值的最大值
$$f(L,R)=max(W_L-f(L+1,R),W_R-f(L,R-1))$$
用DP的方式求一下就可以了
是一个区间DP

有一个模板写法
为了保证可以按照拓扑的顺序计算每个状态，要保证每个状态所依赖的状态先被算出来
比如要算f[L][R]的话，要先把f[L+1][R]和f[L][R-1]算出来
区间DP一般第一维循环，先去枚举长度，长度长的一定是依赖长度短的，因此按照长度从小到大枚举每个区间，就一定可以保证在算每个状态的时候它所依赖的状态都算出来了

时间复杂度是$O(n^2)$的

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N];
int f[N][N];

int main()
{
	scanf("%d", &n);
	//读入n个数
	for (int i = 0; i < n; i ++) scanf("%d", &w[i]);

	//区间DP
	//第一维先枚举长度
	for (int len = 1; len <= n; len ++)
		//第二维枚举左端点
		for (int i = 0; i + len - 1 < n; i ++)
		{
			int j = i + len - 1;
			f[i][j] = max(w[i] - f[i + 1][j], w[j] - f[i][j - 1]);
		}

	//计算总和
	int sum = 0;
	for (int i = 0; i < n; i ++) sum += w[i];
	//计算A-B的差值
	int d = f[0][n - 1];

	//A+B=sum,A-B=d，求A和B
	printf("%d %d", (sum + d) / 2, (sum - d) / 2);
	return 0;
}