P2734 游戏 A Game
有 \(N\) 个正整数的序列放在一个游戏平台上，游戏由玩家1开始，两人轮流从序列的任意一段取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。现在假设两个玩家都采取最优策略，输出最优玩家一和玩家二的最终分数?
例如: \(v = \{8,15,3,7\}\) ，先手拿 \(7\) ,对手拿 \(8\) ；先手再拿 \(15\) ，对手拿 \(3\) 结束，先手拿到的最大价值为 \(7 + 15 = 22\)
思路:
贪心？
显然不行，刚刚的案例如果用贪心的话，先手第一次拿 \(8\) 对手一定拿 \(15\) ，最终先手的值肯定不如刚刚的选法。
想到每次可以选 \(a[i]\) 或者 \(a[j]\) (这里的 \(i\),\(j\) 是指此时的头尾)。
定义 \(f[i][j]\) 为当前的人采取最优策略得到的值，存的值为玩家一与玩家二的差值。
就可以得到转移方程:
\(f[i][j] = max(f[i + 1][j] + a[i],f[i,j - 1] + a[j]])\) (如果当前是玩家一的话)
\(f[i][j] = min(f[i + 1][j] - a[i],f[i,j - 1] - a[j]])\) (如果当前是玩家一的话)
可以通过当前 \(i + j\) 的奇偶性来判断或者传一个参数来标记当前是谁选择。
然后因为是不断向中间逼近，所以这里采用自顶向下的记忆化搜索来写。
最后得到的答案 \(f[1][n]\) 是玩家一和玩家二的差值。
假设玩家一的最终值为 \(x\) ，玩家二的最终值为 \(y\) 。
- 两个玩家的总和一定为全部元素之和: \(x + y = sum\)
- 玩家一和玩家二的差值: \(x - y = f[1][n]\)
通过两个公式就可以得到两个变量的具体值了。
实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 105, Min = -1e9;
int a[N], n;
int f[N][N];
int dfs(int u, int i, int j)
{
if (i == j)
{
if (u)
return f[i][j] = a[i];
else
return f[i][j] = -a[i];
}
if (f[i][j] != Min)
return f[i][j];
if (u)
f[i][j] = max(dfs(u ^ 1, i + 1, j) + a[i], dfs(u ^ 1, i, j - 1) + a[j]);
else
f[i][j] = min(dfs(u ^ 1, i + 1, j) - a[i], dfs(u ^ 1, i, j - 1) - a[j]);
return f[i][j];
}
int main()
{
scanf("%d", &n);
int sum = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++)
f[j][k] = Min;
dfs(1, 1, n);
int dif = f[1][n];
int rex = (sum + dif) / 2;
printf("%d %d\n", rex, sum - rex);
return 0;
}