洛谷P9156 「GLR-R4」芒种题解

题意：

双重神经衰弱 是一个极其考验记忆力的卡牌游戏，其规则如下。

有 $n$ 种不同类型的卡牌，每种两张，初始时这 $2n$ 张牌全部倒扣在桌面上。两位玩家轮流操作，每次操作选择两张不同的牌同时翻起，这两张牌将对双方展示，此后：

若两张牌类型相同，则操作者得 $1$ 分，将这两张牌拿走。下一次操作由当前操作者继续进行。

否则，操作者将这两张牌扣回。下一次操作轮到对方进行。

当所有牌全部被拿走时，游戏结束。

两位玩家的目标都是最大化自己的最终得分。此外，在双方同意的情况下，两人可以选择和局。设和局时还剩下 $2n’$ 张牌，则双方各获得 $n’/2$ 分，游戏结束。为避免游戏无法结束的情况，我们认为：当选择和局同时是双方的最优选择之一时，双方会立即和局。

现在，阿绫和天依想来玩玩这个游戏。因为太饿，负责摆牌的天依不小心把 $2n$ 张牌中的 $m$ 张牌牌面朝上地摆放了，这 $m$ 张牌的的类型恰好两两不同，双方悄悄记住了它们的类型和位置，并将它们扣回，然后开始游戏。我们假定天依和阿绫过目不忘且聪明绝顶，能够记住所有被展示过的牌（包括最初 $m$ 张牌）的类型和位置，也都会采取最优策略最大化自己的期望得分。作为先手方的阿绫想要知道自己的期望得分，你可以帮帮她吗？

由于她们真的要在休息室腻歪好一会儿，所以你需要对 $T$ 组的 $(n,m)$ 分别求出答案。

输入格式：

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $n,m$，分别表示该轮游戏中卡牌的类型数和双方预先翻起并扣回的卡牌张数。

输出格式：

输出 $T$ 行，每行一个实数，表示该组数据的答案。当且仅当你的输出与标准答案的相对误差或绝对误差不超过 $10^{-6}$ 时，被视为正确。

数据范围：

$1\le n\le5\times10^3$，$0\le m\le n$。

这题难度还是蛮高的，尤其是转移方程的推导。（~~剧透了~~）

首先考虑 $n=m$ 的情况。此时仅有 $2n-m = m$ 张牌未知。

结论：此时双方的最优决策都是和棋。下面我们来证明这个结论。

考虑归纳法证明。设 $n~(2\le n \le n_0)$ 时先手期望得分不低于后手，考虑 $n=n_0 + 1$ 的情况。

此时先手显然有三种决策：

选择两张未知牌
选择一张未知牌、一张已知牌
选择两张已知牌

对于第一种决策，因为已知牌中对应的 $n$ 种类型都已经出现，所以此时一定不优。

对于第二种决策，显然是个概率问题，我们来算一下期望（先手的期望得分 $E_n$ ，显然有 $E_n \ge \frac{n-1}{2}$ ）

$\begin{aligned} E_n &= \frac{1}{n}(1 + E_{n-1}) + \frac{n-1}{n}(n - 1 - E_{n-1}) \\[6pt]&=\frac{1}{n}+\frac{(n-1)^2}{n}-\frac{n-2}{n}E_{n-1} \\[6pt]&\le\frac{1}{n}+\frac{(n-1)^2}{n}-\frac{(n-1)(n-2)}{2 n} \\[6pt]&=\frac{2+2 n^2-4 n+2-n^2+3 n-2}{2 n} \\[6pt]&=\frac{n}{2}-\frac{1}{2}+\frac{1}{n} \end{aligned}$

也就是 $E_n \le \frac{n}{2}$ ，不如直接和棋。

对于第三种决策，这一操作仅仅是跳过自己的回合，让后手再次面临决策罢了。$\square$

于是我们考虑一般情况。由于双方得分的和一定为 $n$ ，所以我们可以 dp 他们的期望对于差值，先手为正。

设 $f(n,m)$ 表示 $n$ 对牌中 $m$ 张牌已知时，先手期望得分减去后手期望得分的值。

转移依旧考虑刚刚提到的三种决策

选择两张未知牌 $(2n - m \ge 2)$
$\begin{aligned} f(n,m) &\operatorname{\big\uparrow} \frac{n-m}{\binom{2n-m}{2}}(1 + f(n-1,m)) - \frac{\binom{m}{2}}{\binom{2n-m}{2}}(2 + f(n - 2, m - 2)) \\[6pt]&-\frac{m(2n-2m)}{\binom{2n-m}{2}}(1 + f(n-1,m)) -\frac{2(n-m)(n-m-1)}{\binom{2n-m}{2}} f(n, m + 2) \end{aligned}$
选择一张已知牌和一张未知牌 $(m \ge 1)$

$\begin{aligned} f(n, m) &\operatorname{\big\uparrow} \frac{1}{2 n-m}(1+f(n-1, m-1)) -\frac{m-1}{2 n-m}(1+f(n-1, m-1)) \\[6pt]&-\frac{2 n-2 m}{2 n-m} f(n, m+1) \end{aligned}$

选择两张已知牌 $(m \ge 2)$
$f(n,m) \uparrow 0$
为什么是 $0$ 呢？事实上，在这种决策最优的情况下，双方一定会选择和棋。

其实很显然，因为 $m$ 张是两两不同的，所以如果需要跳过自己的回合，那就是我们之前讲到的那种情况了。

至此，我们已经完成这道题。

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

代码：

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

double dp[N][N]; char vis[N][N];
double dfs(int n, int m)
{
    if(n <= 0 || m < 0 || n < m) return 0;
    double& cur = dp[n][m]; if(vis[n][m]) return cur;
    vis[n][m] = true; cur = -1e233;
    if(m >= 1)
    {
        double sum1 = 1 + dfs(n - 1, m - 1);
        double sum2 = (m - 1) * (1 + dfs(n - 1, m - 1));
        double sum3 = 2 * (n - m) * dfs(n, m + 1);
        up(cur, (sum1 - sum2 - sum3) / (2 * n - m));
    }
    if(2 * n - m > 1)
    {
        double sum1 = (n - m) * (1 + dfs(n - 1, m));
        double sum2 = m * (m - 1) / 2 * (2 + dfs(n - 2, m - 2));
        double sum3 = 2 * m * (n - m) * (1 + dfs(n - 1, m));
        double sum4 = 2 * (n - m) * (n - m - 1) * dfs(n, m + 2);
        up(cur, 2 * (sum1 - sum2 - sum3 - sum4) / ((2 * n - m) * (2 * n - m - 1)));
    }
    if(m >= 0) up(cur, 0.00);
    return cur;
}
void solve()
{
    int n, m; cin >> n >> m;
    cout << ((n + dfs(n, m)) / 2) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(12);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}