[LMXOI Round 1] Placer

· · 题解

挺有意思的题目，难度应该是绿左右。

看到这题第一反应是设 f_i 代表前 i 个括号的最大美丽度。

一时间应该会想到从该右端点匹配的左端点转移过来，设这个左端点为 l，即 f_i = \max (f_{i-1} , f_{l-1} + a_i - a_l)。

想了一会就会发现这漏了情况，形如 ()()() 这样的，按上面的转移就是 f_2 从 f_1 转移过来，f_4 从 f_3 转移过来，f_6 从 f_5 转移过来。

但是 f_6 也可以从 f_1 和 f_3 转移过来。

因此发现一个右端点可以从它前面与它同层的任意一个左端点转移过来。

同层的解释：相同层数且在同一外层中。

相同层数很好理解，举个例子说明什么叫在同一外层中。

(())(())，八个位置的层数分别为 1 2 2 1 1 2 2 1。但两个第二层的括号并不在同一外层中。

(()())，六个位置的层数分别为 1 2 2 2 2 1。此时两个第二层的括号在同一外层中。

到这里，我们就可以写出 O(n^2) 的 dp 了：对于每个右端点 i，枚举所有同层的左端点 j。则 f_i = \max (f_{i-1} , f_{j-1} + a_i - a_j)。时间复杂度 O(n^2)。

观察这个转移方程我们可以把 f_{j-1} - a_j 放到其对应层数的优先队列里，每次转移取优先队列里最大的数。可将复杂度降为 O(n\log n)。

最后一个重要的点是直接这么做会让优先队列里存在不在同一外层中的数，解决方法是退第 i 层后把 i+1 层的优先队列清空。

Code