本文主要是介绍【AcWing】蓝桥杯集训每日一题Day22|区间DP|博弈论|1388.游戏(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1388.游戏
| 1388. 游戏 - AcWing题库 |
|---|
| 难度：中等 |
| 时/空限制：1s / 64MB |
| 总通过数：1429 |
| 总尝试数：1925 |
| 来源： usaco training 3.3 |
| 算法标签 博弈论DP区间DP |
题目内容
玩家一和玩家二共同玩一个小游戏。
给定一个包含 N 个正整数的序列。
由玩家一开始，双方交替行动。
每次行动可以在数列的两端之中任选一个数字将其取走，并给自己增加相应数字的分数。（双方的初始分都是 0 分）
当所有数字都被取完时，游戏结束。
分更高的一方获胜。
请计算，如果双方都采取最优策略进行游戏，则游戏结束时，双方的得分各是多少。
输入格式
第一行包含整数 N。
后面若干行包含 N 个整数，表示这个序列。注意每行不一定恰好包含一个数。
输出格式
共一行，两个整数，分别表示玩家一和玩家二的最终得分。
数据范围
2≤N≤100,
数列中的数字的取值范围为 [1,200]。
输入样例：
6
4 7 2 9
5 2
输出样例：
18 11
题目解析
方案可能不唯一，分值是一样的，每个人都希望分值最高，都绝顶聪明，最终每个人的分值是唯一确定的
每一个选法得到的分值都是唯一确定的
N最大是100
序列中每一个数的最大值是200
博弈论
每一次有两种选择，是选左边的还是右边的呢，左边的就是 w l w_{l} wl，右边的是 w r w_{r} wr
要看条件和目标，目标是要分值尽可能高，由于所有数的总和是一定的
就是一个零和游戏
一方的分值越高，另一方的分值就越低
等价于，一方的分值减去另一方的分值最大，也就是差值最大
就是看选左边的话，差值A-B的最大值是多少，选右边的话，差值的最大值又是多少
两者要取一个max
- 比如选左边的话，剩下的问题就变成了从L+1到R的一个子问题，一个递归的问题
该对手选了，对于对手来说，B-A差值最大是多少，可以求一下，如 S B − A S_{B-A} SB−A
我们减对方的分值就是 − S B − A -S_{B-A} −SB−A再加上当前选择的分值L
因此选左边的话，我们的分值就是 W L − S B − A W_{L}-S_{B-A} WL−SB−A - 同理，如果选右边的话，就变成了一个L到R-1的一个子问题
最终的分值就是 W R − S B − A W_{R}-S_{B-A} WR−SB−A - 两者取一个最大值，就是当前的最大值
博弈论的核心
每次有多种选择，每次选完之后，一定要让最坏情况下最好，也就是我们选完之后，对方一定会选择对他来说最好的情况
在做的时候会发现会产生很多的子问题
可以用一个DP数组，把每一个子问题存起来，比如 S B − A S_{B-A} SB−A
相当于对这个核心策略进行记忆化，就可以形成一个DP
f[L][R]
对于当前LR这个区间，先手分值减后手分值的最大值
f ( L , R ) = m a x ( W L − f ( L + 1 , R ) , W R − f ( L , R − 1 ) ) f(L,R)=max(W_{L}-f(L+1,R),W_{R}-f(L,R-1)) f(L,R)=max(WL−f(L+1,R),WR−f(L,R−1))
用DP的方式求一下就可以了
是一个区间DP
有一个模板写法
为了保证可以按照拓扑的顺序计算每个状态，要保证每个状态所依赖的状态先被算出来
比如要算f[L][R]的话，要先把f[L+1][R]和f[L][R-1]算出来
区间DP一般第一维循环，先去枚举长度，长度长的一定是依赖长度短的，因此按照长度从小到大枚举每个区间，就一定可以保证在算每个状态的时候它所依赖的状态都算出来了
时间复杂度是 O ( n 2 ) O(n^2) O(n2)的
代码
#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和Bprintf("%d %d", (sum + d) / 2, (sum - d) / 2);return 0;
}
这篇关于【AcWing】蓝桥杯集训每日一题Day22|区间DP|博弈论|1388.游戏(C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
