小马恶魔城：C 逃亡

# 题解 for C：逃亡
[C.pdf](http://leanote.com/api/file/getAttach?fileId=5bb635b1ab644147a9004379)
首先我们看看这道题的部分分：

对于$30\%$的数据，我们写个爆搜搜过去就可以了。

对于$60\%$的数据，注意到$n,m$为$100$，且$k\leq 5$。

考虑拆点最短路，对于每一个格子将它拆成$2^{2k}$个点，

用状压表示拿过的精华和已经成为朋友的部落。

在精华处和部落处特殊连边，最后统计最优解。

~~考虑到一定是个网格图，类似BFS的SPFA是很占优的~~

复杂度：$O(SPFA(NM2^{2k}))$

$80$和$100$分的算法是一样的，

$80\%$的数据其实是为了让大家有信心写正解，就算被卡了，还可以有$80$分。

不难发现，$60$分做法有很多格子连着一样的边，复杂度利用率不高。

考虑如何优化状态，我们可以把状态简化。

我们发现只有部落、精华以及起点终点所在的格子才是我们关心的，我们引用一个例子：

![图片标题](https://leanote.com/api/file/getImage?fileId=5bb6354bab644147a9004364)

虽然很明显，什么都不做走到右下角即是最佳方案。但是我们引用这个例子来说明状态的简化。

那么可不可以只保留我们所关心的格子而忽略其他格子呢？当然可以。

我们发现，如果需要和部落交友，一定是高山遮挡关系的缘故。那么我们就可以从每一个关键点开始$BFS$，高山和部落都算是走不通的点，这样就可以预处理出如果什么都不做，关键点之间两两互相到达的最短距离了。我们把所有的关键点拿出来，建一个点数为$2k+2$的图，图中两个关键点之间无向边的边权就是我们预处理的两两关键点的最短距离。

考虑原图上每一个决策，都可以对应新图上的一个决策。原图中不交友无法到达的关键点在新图中依然无法到达，完成后的图基本上是这个样子(只画了局部，用于感性理解)。

![图片标题](https://leanote.com/api/file/getImage?fileId=5bb63554ab644147a9004368)

那么我们在新的图上状压就可以了，每一个点拆成$2^{2k}$个点，表示部落的交友状态和精华的拾取状态 。

在每一个关键点处理对应的状态转移，最后统计到达终点的最优解。

复杂度：$O(kNM+k^22^{2k})$。

Rockdu's Blog

导航

最近发表

大佬们的友链