Brief description: …. 略） Analysis: 。。首先题目中的图有一定误导性。。在中间的任何时刻。。当前位置打开羊圈有两边的羊可以跑出时。。都立即打开当前位置的羊圈。。而不会出现图中那种跳跃的情况。。。注意到初始位置固定。。。 所以状态是。。dp[l][r][2] 表示向左走了 l 步。。向右走了 r 步。。且当前在区间 左/右 端点处时的最优值。。。 。。状态类似 青蛙的烦恼。（参见黑书 p133。 。。转移的时候需要中间未被访问的部分的一段 rmq。。。因为是静态。。所以选择离线 ST。。去掉多余部分。。并做一些位移。。可以一定程度上避免状态转移的时候不小心写疵。。……