洛谷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;
}