序列变换

WeLikeStudying · 2022-04-25 13:42:08 · 题解

• 对自身的问题有了更新的体会。
• 力量生发在沉寂内。

题意

• 题目链接。
• 给一个括号序列（左括号带权），有两个操作可以干：交换两个合法括号序列，不需要代价；把两个相邻的左右括号权值交换，代价是它左边的极长合法括号序列的极左左括号乘 x 加它右边的极长合法括号序列的极右右括号乘 y，而 x,y\in\{0,1\}，给定括号序列要求变成“前面是 n 个左括号，后面是 n 个右括号”的最小代价。

分析

• 既然只有 2\times 2=4 种情况，那么我们就一个一个想！
• 接下来的情况要求我们简化模型。什么模型比较好简化呢？我们想到了这题。似乎可以尝试把括号看成树的欧拉序，然后就转化为树上操作啦。
• 操作 1 相当于任意交换一个节点的所有子树。
• 操作 2 相当于将一个节点和它的所有儿子归到它兄弟的儿子上，代价与这个有关系。
• 操作的目标即得到一条链。

x=0,y=1

• 容易发现几个简单的性质：单调性：每个节点的深度不降，简单性：每次只会改变一个节点的深度。
• 直观上看 x=0,y=1 最简单，因为最终的答案只与每个节点的深度有关，算出每个点的深度，现在目标就变成了给定一个排列 p_i，满足 p_i\ge d_i，且最小化 \sum w_i\cdot (p_i-d_i)，实质是最小化 \sum w_i\cdot p_i。
• 它或许不那么形象（换成树的模型或许形象很多），但是如果从大到小枚举 p_i，目前会挑选哪个在 p_i 层呢？一定是 w_i 最小的吧，但是有一个前提条件，那就是前 i 层必须保留超过 i 个节点，我们当然是贪心地把 目前 w_i 最大的保留，这就是一个简单的 O(n\log n) 贪心算法（让小儿子出远门），代码。
• 接下来或许就不那么简单了，但是我们或许可以对算法作一个有趣的猜测：说不定就全是贪心呢？

x=1,y=0

• 首先可以确定的是：我们完全可以维持一个循环不变的状态，即由上往下地推之后，所有其它节点都是某个节点的儿子（这样总是更有利于我们做出决策的，而且后面可以看到，这种情况下，所有可能的更优解也都循环回这样的情况），如果我们给出一个最终节点排列（首先它得合法）并宣称它是最优情况，那么我们可以贪心地算出最优转移（如果这层滞留 n 个节点，n-2 个以权值最小的一个转移到下一层，1 个以留在这里的权值转移到下一层），枚举所有排列，我们有一个相当简洁的 O(n!\cdot n\log n) 的做法但好像没啥用。
• 我们这个时候试下考虑 x=1,y=0 的情况吧，不论如何，我们可以量化它，计算出第 i 层有 c_i 个节点要向下到达第 i+1 层（c_n=0），不论怎么排列这个总是不变的。
• 你会发现有一些 c_i 为 0（作者曾经一度以为只有 c_n=0，然后发现 (((()))) 这样的序列就可以打我的；脸），而有一些 c_i 非 0，而放在大于 0 的位置的转移贡献至少为 1，其它的贡献都可以由最小的那个数字承担，所以应该贪心地把 c_i=0 的位置由较大的数去填充。
• 当然，哪些较大的数字应该可以到达这里（首先应该得合法），所以我们把这整个序列划分为多个只有末尾 c_i=0 的连续段内部分别处理（显然连续段之间的元素无法互换），贪心的策略仍然是把 c_i=0 交给最大的数，滑动的时候优先以当前最小的数为梯子，复杂度 O(n\log n)，代码。
• 你手工模拟发现并不对劲，在一棵树上实际操作的时候你需要实现两个目标，而两者可能不能兼得：比如说下面这棵树：
• 作者目前唯一的想法就是暴力处理这种情况，因为只需要节点凑齐 3 个就不会出现这种情况，那么除了第一段是二叉那么后面必须要是单链，所以只剩下两种情况：
• 延伸出两条单链：这个只需要作一次决策就可以打破僵局，分类讨论即可，不过可以归纳到后面的情况处理。
• 延伸出一条单链和一个节点，可以利用如果滑动当前后缀最大值就一定要滑动到底部（否则没有效果）的性质优化到 O(n^2)，对于较小值的滑动，我们发现一个简单的事实，就是此时 c_i=1 恒成立，所以它不滑动到最底部（存在反复被其它最小值替换的可能，但那个显然不会作为答案）也是没有办法“服务他人”的，所以最后，我们的结论是：到了真正要做出抉择的时刻（后缀最大值出现，旁边有一个更小的值的时候），你选择一条路就只能把它走到黑……所以最终得到了靠谱的做法，代码。

x=1,y=1

• 感觉要考虑两方面欸，好复杂的样子……虽然枚举所有排列依旧可以贪心……
• 然后你发现转移依靠当前最小值和后缀和，它们都要求尽量让小的放在后面，也就是模拟第一种情况的贪心即可，代码。
• 后悔了，应该先想这一个的。

总结

• 回顾整个思考的过程，感觉三个贪心都是有迹可循的，首先对于整个复杂的模型，你首先得找到一个思路将其简化，然后你要把它具体化，量化，比如说枚举一个排列然后找到它转移依靠什么，这一步之后，你可能会发现它是贪心，也可能找到了别的算法。
• 然后就是检验准确性，结合实际模型判断你的贪心在实际上是能否做出的（比如可能不能同时让两个较优的条件满足）来完善你的贪心，这是细节上的问题，它在考试的时候还是有一定难度的，因为出题人给的数据非常良心。
• 总地来说，帮助很大。