标签：King 联通 times Road 移动 dp

2023-09-28

题目

Road of the King

难度&重要性(1~10):8.5

题目来源

luogu

题目算法

(纯)dp

解题思路

一道非常好而有意思的题目，码量巨短。
首先观察数据范围，发现是 \(n\le 300\)，考虑 \(O(n^3)\) 的 dp。
主要的难点在于如何去判断是否是强联通的。我们知道，dp 是非常难以去记录转移状态的，更何况还要判断是否强联通。
同时这道题只要求 \(O(n^3)\) 的时间复杂度，我们就可以考虑去把这个强联通的条件直接放进 dp 的状态里面。
那么既然考虑将强联通分量放进状态里面去那么就需要我们仔细的考虑这个强联通的性质来转移了。
我们不难发现一下几条简单的证明显然的性质：

• 如果我新移动到的点是我以前经过的点且是与点 \(1\) 是强联通的，那么整个经过的结点就都是与点 \(1\) 强联通的。
• 如果我新移动到的点是我以前到过的点，那么一定会形成一个强联通子图。
• 如果我新移动到的点是我从没有到过的点，那么一定不会与其他点强联通。

好了，我们知道这些性质之后就可以轻松的得到 dp 状态以及转移了。
我们记 \(f_{i,j,k}\) 表示当前已经经过了 \(i\) 个结点，走了 \(j\) 步，存在 \(k\) 个结点与点 \(1\) 是强联通的（包括点 \(1\)）。
转移方程就是：

\[\begin{aligned}f_{i+1,j+1,k} & +=f_{i,j,k}\times (n-i)\\f_{i,j+1,k} & +=f_{i,j,k}\times (i-k)\\f_{i,j+1,i} & +=f_{i,j,k}\times k\end{aligned} \]

这里解释一下为什么这么转移：

• 当新移动到的点是我从没有到过的点，则这时就有 \(n-i\) 种点可供选择。
• 当新移动到的点是我以前经过的点，但不与点 \(1\) 强联通时，有 \(i-k\) 个点可以选择。
• 当新移动到的点是与点 \(1\) 强联通的，那么所有 \(1\sim i\) 就都是与点 \(1\) 强联通的，有 \(k\) 个点可以选择。

然后这道题就 A 了，对没有任何优化，非常有意思也很暴力的 dp。

完成状态

已完成

标签：King,联通,times,Road,移动,dp
From： https://www.cnblogs.com/OIerBoy/p/17736526.html