题解：AT_abc470_e [ABC470E] Concentration

lzm2025 · 2026-08-10 16:42:10 · 题解

题意简述

有一种游戏，桌上有 2n 张牌，有 n 个数 a_1 < a_2 < \dots < a_n，桌面上每个数的牌恰有两张且无法看到牌上的数字。初始生命值为 l，每次操作依次选择两张牌并查看其背面的数 x,y（在选 y 之前可以知道 x）。

若 x = y，获得 x 的得分，去除这两张牌。
否则，生命值减少 1，放回这两张牌。

假定你看完牌后可以一直记住牌上的数，且牌的位置不变。问在最优策略下期望的得分是多少。n,l \le 200。

最优策略

根据贪心，应当立即配对已知可以配对的对，因为这样可以在不掉血的情况下得分。这一步过后，已知的牌上的数字两两不相等。若我们翻一张已知牌，我们无法得到更多信息，故最好的策略是翻一张未知牌，设得到 x_0。

情况 1：若正好有一张已知牌上的数是 x_0，则我们直接翻这两张牌，得分 x_0 且不掉血。
否则，翻出一张已知牌配对的概率为 0，不如翻出一张未知牌 y_0。
- 情况 2.1：若 x_0 = y_0，得分 x_0 且不掉血。
- 情况 2.2：否则，若正好有一张已知牌上的数是 y_0，我们应当在下一回合直接翻这两张牌，得分 y_0 且掉一点血。
- 情况 2.3：否则，这两张牌都变为已知。

代码实现

考虑 DP，设 dp_{i,s,t} 表示当前局面下，剩余 i 点血，s 张牌已知，t 张牌还未知。由于匹配的牌一定是两两配对的，故 t 张牌中的数去掉 s 张牌中的数后一定可以两两配对。故出现情况 1 的概率是 p_1 = \frac{s}{t}；情况 2.1 的要在 \frac{t-s}{t} 的概率下在选完第一个后剩下的 t - 1 个数中选择对应的一个，概率为 p_{2.1} = \frac{t-s}{t} \times \frac{1}{t-1}；情况 2.2 则是要在剩余的 t-1 个中选到已知的 s 个之一，的概率是 p_{2.2} = \frac{t-s}{t} \times \frac{s}{t-1}；情况 2.3 的概率则是 \frac{t-s}{t} 减去情况 2.1 和 2.2 的概率，为 \frac{t-s}{t} - p_{2.1} - p_{2.2}。

由选取的随机性且上述策略和牌上的数无关，每次获得 a_i 的得分的概率均为 \frac{1}{n}，期望为 avg = \frac{\sum_{i=1}^n a_i}{n}。根据上述分析，不难得到 DP 转移方程：

dp_{i,s,t} = \frac{s}{t} (dp_{i,s-1,t-1} + avg) + \frac{t-s}{t(t-1)} (dp_{i,s,t-2} + avg) + \frac{(t-s)s}{t(t-1)} (dp_{i-1,s,t-2} + avg) [i > 1] + \frac{(t-s)(t-s-2)}{t(t-1)} dp_{i-1,s+2,t-2}

边界条件是没血的时候 dp_{0,s,t} = 0 和取完的时候 dp_{i,s,0} = \frac{s \times avg}{2}，初始状态是 dp_{l,0,2n}。转移是 3d-0d 的，时间复杂度 O(n^2 l)。

代码

本题 corner case 比较多，注意 s > t 是不合法状态且避免除以 0 的情况发生。~~官解说的记忆化卡常是假的。~~

#include <bits/stdc++.h>
using namespace std;
int n, l;
double dp[207][407][407];
double a, avg;
double get_dp(int i, int s, int t) { // 记忆化搜索
  if (i == 0 || s > t)
    return 0;
  if (t == 0)
    return (s / 2.0) * avg;
  if (dp[i][s][t] >= -0.5)
    return dp[i][s][t];
  double ans = 0;
  if (t > 0)
    ans += (double)s / t * (get_dp(i, s - 1, t - 1) + avg);
  if (t >= 2)
    ans += (double)(t - s) / (t * (t - 1)) * (get_dp(i, s, t - 2) + avg);
  if (t >= 2 && i > 1)
    ans +=
        (double)(t - s) * s / (t * (t - 1)) * (get_dp(i - 1, s, t - 2) + avg);
  if (t >= 2)
    ans += (double)(t - s) * (t - s - 2) / (t * (t - 1)) *
           get_dp(i - 1, s + 2, t - 2);
  return dp[i][s][t] = ans;
}
signed main() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> n >> l;
  for (int i = 1; i <= n; i++) {
    cin >> a;
    avg += a;
  }
  avg /= n;
  for (int i = 0; i <= l; i++)
    for (int s = 0; s <= (n << 1); s++)
      fill(dp[i][s], dp[i][s] + (n << 1) + 1, -1);
  cout << fixed << setprecision(9) << get_dp(l, 0, n << 1) << '\n';
}