题解：CF2023D Many Games

Pengzt · 2025-01-13 01:15:31 · 题解

Many Games

题目链接。cnblogs。

Problem

给你 n 个物品，每个物品有一个概率 p_i 和权值 w_i。如果选中某个物品 i，那么有 p_i\%~(1\le p_i\le 100) 的概率中奖并获得 w_i， 然后假设你选了一个集合 S，当且仅当集合内的物品都中奖了，才能获得集合内的 \displaystyle\sum_{i\in S} w_i。定义一个集合的价值 f(S) 为

求 f(S) 的最大值。

数据范围：1 \le n \le 2 \times 10^5，1 \le w_i, p_i\cdot w_i \le 2 \times 10^5。

Sol

首先 p_i = 100 的点是一定会选的。然后如果 p_i 相同的话，我一定是从大到小的选择 w_i。然后感觉一下，如果 w_i 相差不大的话，概率越小的数选的个数也会越少，不然一定不优。考虑具体的分析一下这个东西。不妨令当前的物品的概率为 p（此时 p \in (0, 1)），物品的价值为 \large\frac{w_{max}}{100p}（更小肯定更劣），集合中暂时没有数（有数的话影响会更大，因为它会使之前的值变小）。设这类物品选了 x 个，则 f 为 p^x \cdot x \cdot \frac{w_{\max}}{100p} = p^{x - 1}x\frac{w_{\max}}{100}。于是这个东西就只和 p^{x - 1}x 有关。不妨令 g(x) = p^{x - 1}x，则 g'(x) = p^{x - 1}\ln(p)x + p^{x - 1}。当 p^{x - 1} + xp^{x - 1} \ln p = 0 时 g(x) 有最大值。p^{x - 1} = -p^{x - 1}\times x\ln p。x \ln p = -1 时有最小值。则 x = \frac{1}{\ln \frac{1}{p}}。当 p = 0.99 时有最大值 100。最后直接把每个 p 对应的元素全部拉出来跑一遍背包即可。然后这个东西的个数只有五百个左右就做完了。

这道题 double 是够用的，long double 可能会比较卡时间。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template <typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
typedef double ld;
int n;
int w[200005];
ld f[300005];
vector<int> p[105];
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d%d", &x, w + i);
        p[x].emplace_back(w[i]);
    }
    f[0] = 1;
    for (int i = 1; i < 100; ++i) {
        sort(p[i].begin(), p[i].end(), greater<int> ());
        int lim = ceil(1 / log((ld) 100 / i));
        while ((int) p[i].size() > lim)
            p[i].pop_back();
        for (int j : p[i])
            for (int k = 300000; k >= j; --k)
                f[k] = max(f[k], f[k - j] * i / 100);
    }
    ll s = 0;
    for (int i : p[100]) s += i;
    ld ans = 0;
    for (int i = 0; i <= 300000; ++i)
        ans = max(ans, f[i] * (i + s));
    printf("%.8lf\n", ans);
    return 0;
}