巧妙的 DP 题目。
设 $k’=n-k-1$ ，并接下来都是用 $k’$ 。设每种材料被收集的时间为 $t_i$，相当于求 $\displaystyle E(\text{kth}\max_{i=1}^n t_i)$。max 显然不好直接求，考虑 min-max 容斥得到：
其中 $\displaystyle E(\min_{i\in S} t_i)= \frac{m}{\sum_{i\in S} p_i}$。考虑一个暴力 DP，设状态 $f(i,j)$ 表示选择 $i$ 种材料，$\sum_{i\in S} p_i=j$ 的方案数。因为需要每次枚举所有材料。这样的时间复杂度 $\mathcal O(n^2m)$，不能通过。
注意到 $k$ 是很小的。考虑 $k$ 压进去。于是我们直接求容斥系数 $\displaystyle \sum_{\sum_{i\in S} p_i=j}(-1)^{|T|-k}\binom{|T|-1}{k-1}$。因为需要计算 $\frac{m}{f(S)}$ 的贡献，$\sum_{i\in S} p_i$ 还是需要压进状态里，于是考虑设计状态 $f(i,j,k)$ 表示考虑前 $i$ 个数，$\sum_{i\in S} p_i=j$，关于 $k$ 的容斥系数。但是处理组合数似乎令人头疼，尝试利用 $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$，拆一下 $|T|,k$ 的容斥系数，得到：
拆出来的两个是 $|T|-1,k$ 和 $|T|-1,k-1$ 的容斥系数！这就很棒了，因为这个递推关系与 $|T|$ 具体值无关，我们就不用枚举每一种材料了。我们容易得到状态转移方程：
需要注意的是对边界的处理。有用的状态只有 $k>0$。$k=0$ 作为边界，只会被贡献到 $f(i+1,p_i,1)$，新选的产生的容斥系数为 $(-1)^{1-1}\binom{0}{0}=1$，于是边界应为 $f(i,0,0)$。或者换一种角度，从定义出发，$f(i,0,0)=(-1)^{0-0}\binom{-1}{-1}=1$，这里的组合数涉及到负数，需要用到扩展的定义，但依然满足上面的递推式。
滚动数组倒序枚举 $j$ 能够压掉 $i$ 这一维的空间。总的时间复杂度为 $\mathcal O(nmk)$。
代码极短，并且十分好写。
Code
1 |
|