自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:46，当前版本为作者最后更新于2023-03-10 10:10:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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