P4669 [BalticOI 2011] Meetings (Day2)

_Yonder_ · 2025-06-08 11:49:23 · 题解

神秘题。

看到 p,v\le1000 考虑将 dp 的状态与时间相关联。

令 dp_i 表示时间为 i 时的最多成员数。

则 dp_i=\displaystyle\max_{1\le j\le\frac{i-v}{p}}\{dp_{i-v-j\times p}\times j\}。

那么当 dp_i\ge n 时，i 即为答案。

考虑分析复杂度。

后面那个 \times j 是个很好的切入点，相当于我只需要花费 v+j\times p 的代价就可以让答案乘 j。但是这个 dp 是二重循环，所以我们考虑判断一个固定的 j 满足答案需要的复杂度，即 O(\frac{[(v+j\times p)\times\log_jn]^2}{p})。最坏大概是 O(p(e+1)\ln^2n)。