洛谷P2734 [USACO3.3] 游戏 A Game 题解

题意：

有如下一个双人游戏：$N (2 \leq N \leq 100)$ 个正整数的序列放在一个游戏平台上，游戏由玩家 $1$ 开始，两人轮流从序列的任意一端取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。

编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。

输入格式：

第一行: 正整数 $N$，表示序列中正整数的个数。

第二行至末尾: 用空格分隔的 $N$ 个正整数（$1\le N \le 200$）。

输出格式：

只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。

先讲 dp 解法，还是很巧妙的，需要对博弈论理解深刻。

如果我们设 $f_{i,j}$ 表示区间 $[i,j]$ 先手的最优方案，那么有

$f_{i,j} = S_j - S_{i-1}-\min\{f_{i+1,j},~f_{i,j-1}\}$

其中 $S_i = \sum_{j=1}^{i}a_j$ 为前缀和。

为什么需要减去 $f$ 呢？因为如果先手取了 $a_i$ ，那后手的最优方案就是 $f_{i+1,j}$ ，因为先后手转换了。

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(105))

int n, a[N], sum[N], dp[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i]; sum[i] = a[i] + sum[i - 1]; dp[i][i] = a[i];
    }
    for(int i = n - 1; i; i--)
        for(int j = i + 1; j <= n; j++) {
            dp[i][j] = sum[j] - sum[i - 1] - min(dp[i + 1][j], dp[i][j - 1]);
        }
    cout << dp[1][n] << ' ' << sum[n] - dp[1][n] << '\n';
    return 0;
}

然后来讲贪心的解法。

不知道大家有没有觉得这道题很熟悉，之前有道题也是两头取，但是中间的数是存在一定单调性的。

考虑最简单的情况，即 $n=3$ 时，若 $a_2 > a_1$ 且 $a_2 > a_3$

那么先手能比后手多取到 $a_1 + a_3 - a_2$ ，于是我们把它看作一个数

即对于所有 $a_i > a_{i-1}$ 且 $a_{i} > a_{i + 1}$ 的 $i$ ，我们把 $a_{i-1},~a_{i},~a_{i+1}$ 缩成一个数 $a_{i+1}+a_{i-1}-a_i$ 。

重复执行这个过程直到 $a_i$ 成为关于 $i$ 的单谷函数，这样我们就可以贪心地从两头取了。

这样的做法唯一奇怪的地方就是我们真的可以这么缩这些数吗？事实上是可以的。

证明：

对于某个满足条件的 $i$ ，我们将它缩数后，它可能成为单谷函数的某一侧甚至谷部

当然它也可能成为一个新的峰的某一部分，而最终我们会将每个峰都拍成谷的一部分。$\square$

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int sum,top,stk[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x; sum += x; stk[++top] = x;
        while(top >= 3 && stk[top - 1] >= stk[top] && stk[top - 1] >= stk[top - 2]) {
            stk[top - 2] = stk[top] + stk[top - 2] - stk[top - 1], top -= 2;
        }
    }
    int l = 1, r = top, res = 0;
    while(l <= r)
    {
        if(stk[l] > stk[r]) res += stk[l++]; else res += stk[r--];
        if(l > r) break;
        if(stk[l] > stk[r]) res -= stk[l++]; else res -= stk[r--];
    }
    cout << (sum + res) / 2 << ' ' << (sum - res) / 2 << '\n';
    return 0;
}