uoi-r2 T3

happybob · 2022-12-15 17:24:31 · 个人记录

作者：看什么看。

不妨考虑 dp，记前 i 类算法学 j 道题的最小时间为 dp_{i,j}。

不难得到 dp_{i,j}=\min\limits_{l=1}^j(dp_{i-1,j-l}+f_{i,l})，其中 f_{i,l} 表示第 i 类算法中学习 l 道的最小用时。

考虑求 f_{i,l}，设第 i 类算法中原用时从小到大分别是 v_1,v_2,\cdots,v_{p}，则选前 l 个显然是最优的，而且时间长的肯定要先学（要不然就被“加成”了），所以 f_{i,l}=v_l+2\cdot v_{l-1}+\cdots+l\times v_1。

答案就是使 dp_{m,i}\le n 的最大 i。

这样写就足够了，时间复杂度 O(mk^2)。

但是还有一些优化，首先就是观察到 f_{i,l}=f_{i,l-1}+v_1+v_2+\cdots+v_l，其次就是当 f_{i,l}>n 时，其之后的 f 都不必讨论。

优化后，令 s=\min(k,m\sqrt{n})，则时间复杂度 O(k\lg k+ms^2)。