题解：CF2062F Traveling Salescat

· · 个人记录

发现题目中的 \max 和不能经过重复的点非常的诡异，于是先考虑 \max 有什么性质。

不妨先把 \max\{a_i+b_j,a_j+b_i\} 更改为 \max\{a_i-b_i,a_j-b_j\}+b_i+b_j，同时令 c_i=a_i-b_i。

然后我们就发现一件事情：假设路径首尾固定，肯定是在一个 c_i 和一个比它大一点的 c_j 匹配（除了首尾外）。

原因：我们肯定是希望答案最小，而 b_i 的贡献是一定的，=2(\sum_i b_i)-b_s-b_t。贡献大小此时只由 \max 决定。

于是就考虑一个数列，可以任意重排，什么时候 \sum_{i>1}\max\{c_i,c_{i-1}\} 最小。

可以发现一定是在 c_{i-1}\leq c_i 的时候最小。

但是，如果固定 s,t，我们不一定可以达到完全升序。

所以这时候，我们肯定是除了 s,t 之外的点都是升序。

大概可以长成如下：


Min      s     t     Max
  <-------
---------------------->
                <------

于是我们只需要先按照 c_i 排序一遍。然后自然要考虑 dp。这时候，我们发现，上面的那个 c_i 升序的结论，刚好符合了不经过重复点。

当然排序完之后下标也还了。

考虑设计 f_{i,j,c} 表示我们 dp 到了前 i 个点，选了 j 个，c 表示一个状态：0 表示我们在 \text{Min}\to s 这一段，1 表示我们在 s\to t 这一段，2 表示我们在 t\to \text{Max} 这一段。到 \text{Max} 截至为3。

转移就像上面分类讨论一下即可。

代码：