P8820 [CSP-S 2022] 数据传输

tmuxvs5t · 2022-11-02 21:21:27 · 题解

读题

读完题之后 k=1 就会了。

可以说是白送的。

讨论 k=2,k=3 时的情况。

当 k=2 时：

假设结点 u 转移到不在询问链上的节点 k。

我们可以发现，绕两步还不如一步直接走来的快。

换句话说就是 u-k-v 不如 u-v

所以我们可以判定 k=2 时仍然可以在单个链上dp。

由于没有节点的值是负的，k=2 情况似乎也解决了，那就是在这条链上线性dp。

至此，恭喜你拿到了所有暴力分。

当 k=3 时：

发现此时貌似可以转移到链的外部。

具体来说是这样的：

红色的是naive的转移。

绿色是贪心的转移。

蓝色是另一种转移。

可以发现，使用蓝色策略似乎可以绕过一些点，使得答案更优。

所以考虑设计一个dp来计算这件事。

设计 k=3 时的 dp

容易发现，跳出链的充要条件是和链的距离不超过1。

所以我们需要预处理出节点 u 周边权值最小的节点 w_u 。

一遍dfs即可。

接下来考虑设 dp_{u,k} 表示考虑到了节点 u ，目前距离节点 u 距离为 k 的dp最小值。

考虑 k=0,1,2 三种情况。

如上图，当 k=0 时，当前节点的值可以从前面的值（距离不超过3）里转移。

具体来说就是：

如上图，当 k=1 时，当前节点的值可以从前面的值里转移。

但是。。这次要分为两种情况。

当转移到左边黑方框时：

容易发现，此时 dp_{u,1}=dp_{u-1,0} 。

当转移到上面黑方框时：

注意我们在开篇谈到的问题。。

蓝色是另一种转移。

可以发现，使用蓝色策略似乎可以绕过一些点，使得答案更优。

蓝色策略是什么策略？

是跨度为3的转移。

所以我们断定，此时 dp_u=dp_{u-1,1}+w_u 。

综合一下，得到此状态最终解 dp_u=\min\{dp_{u-1,0},dp_{u-1,1}+w_u\} 。

不会放过任何一个使萌新懵圈的点。

为什么可以直接用 w_u ？

我们在开篇定义的是 w_u 表示为 节点 u 周边权值最小的节点 w_u 。

而现在我们期望的是除了 u-1,u+1 以外最小的节点。

为什么这个地方可以 ignore 过去？

由于我们的dp认为 w_u 就是 除了 u-1,u+1 以外最小的节点，

所以我们考虑将 u-1,u+1 分别赋予这个节点。

我们考虑让 w_u=u-1 ，可以发现，u上方的值只能是 f_k+f_{u-1} ，而u左边的值可以是 f_k+f_{u-1} 。在同一起跑线的（深度相同）情况下，左侧的转移严格不劣。

也就是说上方的 w_u 转移完全不会对答案产生任何影响。ignore掉。

再次考虑让 w_u=u+1 , 比起上次，除了 w_u 转移的深度更靠后的以外，基本没什么区别。

综上，我们可以严格证明出使用 w_u 代替 “节点 u 周边权值最小的节点 w_u”的完全合理的。