Game Rooms 题解

题目链接

简要题意

一个 $N$（$N\le4000$）层的大楼，每层只有一个游戏室，可以设置一个乒乓球桌或游泳池。第 $i$ 层有 $T_i$ 个人喜欢乒乓球和 $P_i$ 个人喜欢游泳。 现在要求使每个人到最近的喜欢的类型的活动室的距离的和最小，这里的距离指楼层差的绝对值。

题解

我们把每层的安排看成 $0$ 和 $1$ 中的一个数，则安排就可以看成一个 $01$ 序列 $a$ 。我们发现，对于一个极大的连续 $0$ 串或 $1$ 串，我们可以快速地统计这段需要的代价。具体来说，设 $a_{l-1}=a_{r+1}=1$，$a_l=a_{l+1}=\cdots=a_{r}=0$，$mid=\frac{l+r}{2}$，由于这段数有一半离左端点更近，另一半离右端点更近，则有这一段的代价为：

$\begin{aligned} &\sum_{i=l}^{mid}(i-l+1)\times T_i+\sum_{i=mid+1}^r(r-i+1)\times T_i\\ =& \sum_{i=l}^{mid}i\times T_i-\sum_{i=mid+1}^ri\times T_i+(1-l)\times \sum_{i=l}^{mid}T_i+(1+r)\times \sum_{i=mid+1}^{r}T_i \end{aligned}$

利用二维前缀和统计即可。

于是把这个序列看成一堆极大的连续 $0$ 串和连续 $1$ 串，设 $f[i][0/1]$ 表示第 $i$ 个数是某一个极大连续 $0/1$ 串的结尾的情况下，前 $i$ 个数的最小代价。则枚举这个极大串的左端点即可转移，有转移方程式

$f[i][k]=\min_{j=0}^i(f[j][k \; \mathrm{xor} \; 1]+calc(j+1,i,k))$

其中 $calc(i,j,k)$ 表示第 $i$ 个数到第 $j$ 个数是一个极大的连续 $0/1$ 段的代价，前文已经讨论了如何 $O(1)$ 计算。

时间复杂度 $O(n^2)$.