洛谷 P14259 兄妹（siblings）题解
在 洛谷 上看。
声明：本文章需经作者允许方可转载。
最崩不住的一题。我这个分析虽然愚蠢但是易懂。
思路
首先我们发现，同一排的书架由一个人取是最好的，那么这部分的时间即可求出，定义第 i i i 排从 ( i , 0 ) (i,0) (i,0) 开始取走这排所有的书的时间叫做 r i r_i ri， r i = ∑ j = 1 500 f i , j displaystyle r_i=sum_{j=1}^{500}f_{i,j} ri=j=1∑500fi,j，其中 f i , j f_{i,j} fi,j 表示是否有书。这样就变成了个一维的问题。
然后我们继续观察，发现最远的有书的那一排必须有一个人去取，设那一排横坐标为 p p p，那么这样一个人在纵坐标为 0 0 0 中行走的路程就已经确定了，不如设小 Y 是要这样走。那小 S 就不确定，那么就枚举。
枚举小 S 最远走到第 i i i 排，如果这排没有书，答案一定不优。那小 Y 第 i + 1 ∼ p i+1sim p i+1∼p 排的书都要包了。此时设小 Y 走的时间为 2 ( p + r i + 1 + ⋯ + r p ) + x 2(p+r_{i+1}+dots+r_p)+x 2(p+ri+1+⋯+rp)+x，小 S 走的时间为 2 ( p + r i ) + y 2(p+r_i)+y 2(p+ri)+y，此时 x + y = r 1 + r 2 + ⋯ + r i − 1 x+y=r_1+r_2+dots+r_{i-1} x+y=r
