P9144 [THUPC 2023 初赛] 最后的活动

· · 题解

P9144 [THUPC 2023 初赛] 最后的活动

设 f_i 表示恰好凑到 i 的概率，f_0 = 1。用 f_0\sim f_{i - 1} 递推 f_i。

我们直接模拟一轮迷宫的过程，在每个决策处取概率较大值，出迷宫就认为概率是 f_{i - c}，其中 c 表示本轮迷宫获得的分数。问题在于 c 可能等于 0。这种情况下，如果我们给 f_i 赋初值，那么得到的 f_i 相较于初值一定更偏向于真实值，这是因为决策时 f 的系数在 [0, 1) 之间（不可能取到 1，因为 u_1 + u_2 和 v_1 + v_2 均大于 0，即总有概率得分），所以如果 f 偏离真实值，那么偏离的部分会因为乘上了 [0, 1) 之间的系数而减小，使得答案偏向真实值。

直接迭代需要很多轮才能收敛，根据单调性将迭代换成二分就可以接受了。

时间复杂度 \mathcal{O}(2 ^ nM\log \frac 1 {\epsilon})。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

bool Mbe;
constexpr int N = 8;
constexpr int M = 1e4 + 5;
int n, m, c, s1[N], s2[N];
double u0[N], u1[N], u2[N], v0[N], v1[N], v2[N], f[M];
double dfs(int pos, int acc, int aim) {
  if(pos > n) return 0;
  auto F = [&](int c) {return c > aim ? 0 : f[aim - c];};
  double p1 = max(F(acc + s1[pos]), dfs(pos + 1, acc + s1[pos], aim));
  double p2 = max(F(acc + s2[pos]), dfs(pos + 1, acc + s2[pos], aim));
  int sc = acc * c / 100;
  double u = u0[pos] * F(sc) + u1[pos] * p1 + u2[pos] * p2;
  double v = v0[pos] * F(sc) + v1[pos] * p1 + v2[pos] * p2;
  return max(u, v);
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif

  cin >> n >> m >> c;
  for(int i = 1; i <= n; i++) {
    cin >> s1[i] >> s2[i];
    cin >> u0[i] >> u1[i] >> u2[i];
    int su = u0[i] + u1[i] + u2[i];
    u0[i] /= su, u1[i] /= su, u2[i] /= su;
    cin >> v0[i] >> v1[i] >> v2[i];
    int sv = v0[i] + v1[i] + v2[i];
    v0[i] /= sv, v1[i] /= sv, v2[i] /= sv;
  }
  f[0] = 1;
  for(int i = 1; i <= m; i++) {
    double l = 0, r = 1;
    for(int _ = 0; _ <= 30; _++) {
      double m = (l + r) / 2;
      f[i] = m;
      if(dfs(1, 0, i) < m) r = m;
      else l = m;
    }
    printf("%.9lf ", f[i]);
  }
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}