题解：P11469 校园跑
Falashiro
·
·
题解
设 f_{i,j} 表示剩余 i 次获取点位的机会，当前点位最小跑动距离为 a_j 时最后跑动距离的期望的最小值，设 g_i=\sum\limits_{j=1}^mp_j\times f_{i,j}。易知 f_{0,i}=a_i。
当 i>0 时，有：
\begin{aligned}
f_{i,j}&=\min\{a_j,\sum\limits_{k=1}^mp_k\times f_{i-1,k}\}\\
&=\min\{a_j,g_{i-1}\}
\end{aligned}
我们可以将 a 序列从小到大排序，则存在整数 k\in[1,m]，使得：
\left\{
\begin{aligned}
a_j\ (j\le k)\\
g_{i-1}\ (j>k)
\end{aligned}
\right.
于是有：
\begin{aligned}
g_i&=\sum\limits_{j=1}^mp_j\times f_{i,j}\\
&=(\sum\limits_{j=1}^kp_j\times a_j)+(\sum\limits_{j=k+1}^mp_j)\times g_{i-1}
\end{aligned}
设 s_i=\sum_{j=1}^ip_j，w_i=\sum_{j=1}^ip_j\times a_j，则：
\begin{aligned}
g_i=w_k+(1-s_k)\times g_{i-1}
\end{aligned}
即：
\begin{pmatrix}
g_{i}\\
1
\end{pmatrix}
=
\begin{pmatrix}
1-s_k&w_k\\
0&1
\end{pmatrix}
\begin{pmatrix}
g_{i-1}\\
1
\end{pmatrix}
显然随着 i 的增加，g_i 单调不增，k 单调不增，那么 k 至多变化 m-1 次。
对于 k 相同的一段，我们可以通过矩阵快速幂以 \Theta(\log n) 的时间复杂度求出一个 g 的值，结合倍增，则能够以 \Theta(\log n) 的时间复杂度求出最小的满足 g_i<a_k 的 i，即下一个 k 变化的分界点。而 k 至多变化 m-1 次，于是我们可以以 \Theta(m\log n) 的时间复杂度求出 g_n，g_n 即为最终答案。