题解 CF2229G Roadworks

· · 题解

题解 CF2229G Roadworks

本场其他题

upd on 2/6/2026：修了 typo，“好客的”是 hospitable。感谢审核员指出。

简要题意

英语小课堂：hospitable 有一个意思是“好客的”。

有 n 个地点排成一排，第 i 个有好客度 h_i。每相邻两个地点间有道路，道路 (i,i+1) 在第 d_i 天建成。你从地点 x 出发，每天可以移到相邻的地点（如果两地点间有道路）或者不动，然后你的满足感会增加你这一天结束后所在地点的好客度。求 k 天后最大的满足感。

数据范围：多测，t\le 10^4,\sum n\le 2\times 10^5,k\le 10^9。

做法

竞选最招笑选手：较快地完成了状态设计及 O(n^2) DP，然后花费三小时没想到怎么优化转移。

做这个题，只需要把握一个贪心的思路：对于同一天，我不可能凭着 h 大的不待，待在 h 小的上（当然这个“同一天”不太严谨，大意就是能用一天大的换一天小的就要换）。这样本题的几个 claim 就都能自然一些了。

注意到 k 巨大，所以我们猜想可能的方案就是到达某个位置后在那里赖到最后。于是我们可以调整的部分就是怎么到那个位置。

首先，我们“赖在”的位置一定是 x 到其方向的前缀最大值。因为一条路没修好，影响的是一整个后缀，也就是对于 x 的同一个方向，更远的点不可能先到，所以如果我们选了一个不是前缀最大值的，那我们可以用更少的时间去到达一个更大的，我们不如赖在这个更大的。

而它既然是前缀最大值，那沿着刚才的思路，我在到达它之前不会到达更大的（同样，否则我为什么不留在更大的呢），于是根据贪心原则，我们一定会尽早到达。这个尽早的时间（设为 arr_i）可以考虑我就一直往这一个方向走，没路就等着的用时，可以扫一遍求出。

于是容易想到一个 DP：设 dp_i 表示尽早到达 i 的最大满足感。对于每个可能最终“赖在”的位置，枚举 arr 比它小的所有位置 j 并考虑从这些位置转移过去。根据贪心原则，我想在能尽早到达 i 的基础上尽可能晚出发，所以有方程：

dp_i=\max_{arr_j\le arr_i-\text{dis}(i,j)}\left\{dp_j+h_j\cdot(arr_i-\text{dis}(i,j))+\sum_{l\in (j,i]}h_l\right\}

其中 \text{dis}(i,j) 表示 i 到 j 的距离。为了方便，以上不妨设了 i<j，实际编码时应注意。

这个东西是 O(n^2) 的（里面的 \sum 用前缀和），可以用一些科技做到 O(n\log n) 或者 O(n) 等，这里不展开。

但是不想用科技的你发现这个东西有很多 j 是没有意义的。事实上，因为除非要越过 x，否则改变方向一定是不优的（不如留在某个前缀最大值上），所以可以考虑用自己更新别人的方式，只向左右分别找第一个，这样每个点就只转移两个点，单组复杂度就是 O(n) 了。