[APIO2013]机器人[搜索、斯坦纳树]

题意

题目链接

分析

  • 记 g(d,x,y) 表示从 (x,y) 出发,方向为 d 到达的点,这个可以通过记忆化搜索求出,注意如果转移成环(此时向这个方向走没有意义)要特判。

  • 记 f(l,r,x,y) 表示 \([l,r]\) 的机器人同时位于 (x,y) 最少需要花费多少步,根据题意容易得到转移:

    \[\begin{cases}f(l,r,x,y)=\min\limits_{i=l}^{r-1}\{f(l,i,x,y)+f(i+1,r,x,y)\}\\f(l,r,x,y)=\min\limits_{g(d,a,b)=(x,y)} \{f(l,r,a,b)\} \end{cases}​\]

    其实这就是一个斯坦纳树形象的表现形式。

  • 朴素的 \(dijkstra\) 写完之后会 TLE。似乎此题还有一个没有用到的潜在条件:最短路的边权是1。

    想法类似 noip2016蚯蚓 。首先将所有初始点按照 f 排序放到队列,由于边权是1,我们可以保证新加入队列的点的 f 一定是单调不降的,此时我们可以维护两个有序的队列 q1, q2,其中 q1 是所有初始点,q2 是更新得到的点,仍然跑 dijk ,这样常数会小很多(如果采用桶排会更快?)。

代码

代码链接

上一篇:[APIO2013]机器人(斯坦纳树)


下一篇:BZOJ3205/UOJ107 [Apio2013]机器人