P7430 [THUPC2017] 组合数问题

· · 题解

这是一个不用凸包的非常容易的题解。

先对题目中的式子进行一个转化。

\begin{aligned} &\max_{S\subseteq [N],|S|=R}\left(\min_{A,D\in\Z^+}\dfrac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\right)\ge x\\ \Leftrightarrow&\exist S\subseteq [N]\land|S|=R,\forall A,D\in\Z^+,\dfrac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\ge x\\ \Leftrightarrow&\exist S\subseteq [N]\land|S|=R,\forall A,D\in\Z^+,\exist i\in S,A\times d_i+D\times a_i\ge x\left(\max_{j\in [N]}(A\times d_j+D\times a_j)\right)\\ \Leftrightarrow&\exist S\subseteq [N]\land|S|=R,\forall A'\in\R^+,\exist i\in S,A'\times d_i+a_i\ge \max_{j\in [N]}(xA'\times d_j+xa_j)\\ \color{red}\textbf{(!): }\color{CandyBar}\Leftrightarrow&\exist S\subseteq [N]\land|S|\le R,\forall A'\in\R^+,\exist i\in S,\forall j\in [N],A'\times d_i+a_i\ge xA'\times d_j+xa_j\\ \end{aligned}

考虑枚举所有的 (i,j)，怎么拓展？发现最后一式，当 (i,j) 固定时，A' 不是在 [v,+\infty) 内，就是在 (0,v] 内，取决于 v=d_i-xd_j 的符号。

考虑对于每个 i，得到这个 A' 的范围，最后做一个 dp，因为左端点是 0，右端点直接看在 r 个内能否覆盖到 +\infty 就行了。

注意特判 d_i-xd_j=0 的情况。

复杂度 \Theta(Tn^2\log V)，跑了 3.38s。