专栏文章

题解：CF2062F Traveling Salescat

____Dice___
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min48n8j
此快照首次捕获于
2025/12/01 20:18
3 个月前
此快照最后确认于
2025/12/01 20:18
3 个月前
查看原文
发现题目中的 max⁡\max 和不能经过重复的点非常的诡异，于是先考虑 max⁡\max 有什么性质。
不妨先把 max⁡{ai+bj,aj+bi}\max\{a_i+b_j,a_j+b_i\} 更改为 max⁡{ai−bi,aj−bj}+bi+bj\max\{a_i-b_i,a_j-b_j\}+b_i+b_j，同时令 ci=ai−bic_i=a_i-b_i。
然后我们就发现一件事情：假设路径首尾固定，肯定是在一个 cic_i 和一个比它大一点的 cjc_j 匹配（除了首尾外）。
原因：我们肯定是希望答案最小，而 bib_i 的贡献是一定的，=2(∑ibi)−bs−bt=2(\sum_i b_i)-b_s-b_t。贡献大小此时只由 max⁡\max 决定。
于是就考虑一个数列，可以任意重排，什么时候 ∑i>1max⁡{ci,ci−1}\sum_{i>1}\max\{c_i,c_{i-1}\} 最小。
可以发现一定是在 ci−1≤cic_{i-1}\leq c_i 的时候最小。
但是，如果固定 s,ts,t，我们不一定可以达到完全升序。
所以这时候，我们肯定是除了 s,ts,t 之外的点都是升序。
大概可以长成如下：
CPP

Min      s     t     Max
  <-------
---------------------->
                <------
于是我们只需要先按照 cic_i 排序一遍。然后自然要考虑 dpdp。这时候，我们发现，上面的那个 cic_i 升序的结论，刚好符合了不经过重复点。
当然排序完之后下标也还了。
考虑设计 fi,j,cf_{i,j,c} 表示我们 dp 到了前 ii 个点，选了 jj 个，cc 表示一个状态：0 表示我们在 Min→s\text{Min}\to s 这一段，1 表示我们在 s→ts\to t 这一段，2 表示我们在 t→Maxt\to \text{Max} 这一段。到 Max\text{Max} 截至为3。
转移就像上面分类讨论一下即可。
代码：
CPP

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...