P17167

__Eureka__ · 2026-08-07 16:52:03 · 题解

我请大家吃 Obsidian。

P16913 [JLCPC 2026] Map1e

Solution

观察到每条线缆一定可以看作由三部分组成，第一个是左端点向左走，再回头，第二个是右端点向右走再回头，第三个是左右端点之间的部分（一个依据是不可能是左端点向右延伸而右端点向左延伸）。那我们可以发现左右端点的贡献是独立的，为啥我没想到呢？我已经菜完了！！！。

那么问题就变成了：要对 n 个字符做括号匹配，如果一个第 i 个字符是 (，那他的贡献是 l_i 否则是 r_i。那我们要做的其实就是决策每一个字符究竟是什么，也就是决策他的种类，并要求对于每一个前缀都有其中的 ( 数量大于等于它长度的一半，一个套路的想法是先都钦定他是那种，必要或存在更优时再改。而此题中括号匹配的条件已经足够严格了，所以只要在必要时加入就好了。

Gain

• 多手模，观察性质（独立性）。
• 要决策种类时，先钦定一个种类再考虑再必要时或更优时反悔。