上界卡不来,怎么这么菜???
下文的概率都是指的 \(\frac{p}{100}\)。
首先有一个想法就是直接背包,但是 \(\prod p\) 涉及不小的数的乘积并不好放入状态,所以考虑设 \(f_s\) 表示 \(\sum w = s\) 的最大概率,但这样只能做到 \(O(n^2V)\)。
分析背包为什么会这么烂:
- 物品数量为 \(n\)。
- 值域上界为 \(nV\)。
这题的题面看着就很精简,似乎无法有更好的解法了,于是尝试从这两个方向来优化。
考虑到这个左侧 \(\prod p\) 的形式,感受一下如果放了很多 \(p\) 很小的物品感觉就比较劣,于是可以尝试对每个 \(p\) 卡一个上界——即算出每个 \(p\) 至多放多少个。
错误的卡上界方式:
不妨认为 \(w = 1 / p\),那么选 \(k\) 个的答案肯定需要比选 \(1\) 个大,就需要满足 \(p^k\times kw = kp^{k - 1} > 1\)。
正确的卡上界方式:
考虑类似背包一个一个放入,那么答案需要递增,否则如果答案不升,概率还更小了一定不优,于是可以得到不等式 \(kp^{k - 1} > (k - 1)p^{k - 2}\),解得 \(k < \frac{1}{1 - p}\)。
当 \(p = 1\) 时这个式子会 \(/0\),不过分析一下 \(p = 1\) 就等同于送自己的,一定会选上,那么可以直接忽略掉。
同时因为答案式子后面是 \(\sum w\),在 \(p\) 相同的情况下,贪心的想法可以知道肯定会尽量选 \(w\) 大的,于是现在就已经可以知道每个 \(p\) 会选多少个并且怎么选了,总共可能选的元素个数为 \(\sum\limits_{i = 1}^{99} \lfloor\frac{100}{100 - i}\rfloor = 481\)。
不过此时如果直接背包也还是 \(\mathcal{O}(m^2V)\) 的,于是继续考虑去卡值域的上界。
错误的卡上界方式:
认为上界 \(= \sum\limits_{i = 1}^{99} \lfloor\frac{100}{100 - i}\rfloor\lfloor\frac{2\times 10^5}{i}\rfloor\)。
正确的卡上界方式:
上面的做法明显是投机取巧啊,除了我真的会有人这么干吗(。
考虑类似上文的方法,考虑令 \(s = \sum w, t = \prod p\),如果删掉一个物品 \((p, w = 1 / p)\) 不劣,那肯定不行,那么有 \(st > (s - 1 / p)\frac{t}{p}\),解得 \(s <\frac{1}{p(1 - p)}\)。
这个函数在 \(p = 0.01 / 0.99\) 时(因为有定义域限制)取到最值,并且注意把 \(1\) 替换成 \(2\times 10^5 / 100 = 2\times 10^3\),得到 \(s\le 202020\)。
此时就可以跑背包了,记 \(m = 481, W = 202020\),时间复杂度为 \(\mathcal{O}(n\log n + mW)\)。
#include <bits/stdc++.h>using f128 = long double;constexpr int V = 202020;f128 f[V + 1];
std::vector<int> w[100];int main() {int n, sum1 = 0;scanf("%d", &n);for (int i = 1; i <= n; i++) {int p, _w;scanf("%d%d", &p, &_w);if (p == 100) {sum1 += _w;} else {w[p].push_back(_w);}}f[0] = 1.0;for (int _p = 1; _p <= 99; _p++) {std::sort(w[_p].begin(), w[_p].end(), std::greater<>());f128 p = 1.0L * _p / 100;for (int i = 1; (1.0L - p) * i < 1.0L && i - 1 < w[_p].size(); i++) {for (int j = V; j >= w[_p][i - 1]; j--) {f[j] = std::max(f[j], f[j - w[_p][i - 1]] * p);}}}f128 ans = 0;for (int s = 0; s <= V; s++) {ans = std::max(ans, f[s] * (s + sum1));}printf("%.10Lf\n", ans);return 0;
}