先让 \(p\) 除以 \(100\)，相当于给你两个数组 \(p, w\)，然后要选择下标集合 \(S\)，使得：
\(p\) 的积乘上 \(w\) 的和最大化。
注意到 \(p_i\) 是整数，并且 \(1\le p_i \le 100\)。
那么容易想按照 \(p_i\) 分类。
然后 \(w_i\) 对于固定 \(p\) 一定是选择排序后的最大值后缀。
目前 \((P,Q)\)，考虑选择 \(i\)：
\[P\cdot W \to P\cdot p_i\times(W+w_i) \]一定是后面的式子大于前面的式子才会选择，考虑做比例，那么不等式就是：
\[p_i+\frac{p_i\cdot w_i}{W} > 1\\ p_i\cdot w_i>(1-p_i)\cdot W \]把 \(p\) 再乘回去：
\[p_i\cdot w_i>(100-p_i)\cdot W \]题意有：\(p_i\cdot w_i \le 2\cdot 10^5\)。
所以 \(W\) 最后不会很大，只会在 \(2\cdot 10^5\) 以内。
然后我们考虑按 \(p_i\) 分类。
假设选择了某个 \(p_i\) \(c\) 个，然后考虑选入的最小的值是 \(w_i\)，考虑它不能删除时：
令：\(q_i=p_i/100\)：
\[P\cdot q_i^c\times(W+w_i\cdot c+\Delta) > P\cdot q_i^{c-1}\times(W+w_i\cdot(c - 1) + \Delta)\\ q_i\cdot(W+w_i\cdot c+\Delta) > W+w_i\cdot(c - 1) + \Delta\\ (q_i-1)\cdot w_i\cdot c > (W + \Delta)(1-q_i) -w_i \]然后只需要考虑 \(\Delta=0\) 的情况，限制更加严格：
\[(q_i-1)\cdot w_i\cdot c > W(1-q_i) -w_i\\ c < -\frac{W}{w_i}+\frac{1}{1-q_i}<\frac{100}{100-p_i} \]也就是说对于一种概率 \(p_i\) 的物品，最多选择 \(\frac{100}{100-p_i}\) 个
\[\sum_{i=0}^{99}\frac{100}{100-p_i} = 100\ln 100\approx482 \]然后对于概率等于 \(100\) 的物品无脑全部选入即可。
这里直接用 \(dp_{i,j}\) 表示考虑完前 \(i\) 种物品，目前 \(W=j\) 时的最大的 \(P\)。
最终复杂度就是 \(O(2\cdot 10^5\times 482)\)。
标签：frac,cdot,Many,CF2023,times,Games,Delta,100,考虑 From： https://www.cnblogs.com/weirdoX/p/18491764