1 条题解
-
1
题意
- 题目链接。
- 给一个括号序列(左括号带权),有两个操作可以干:交换两个合法括号序列,不需要代价;把两个相邻的左右括号权值交换,代价是它左边的极长合法括号序列的极左左括号乘 加它右边的极长合法括号序列的极右右括号乘 ,而 ,给定括号序列要求变成“前面是 个左括号,后面是 个右括号”的最小代价。
分析
- 既然只有 种情况,那么我们就一个一个想!
- 答案为
出题人大概率不会给这个部分分。 - 接下来的情况要求我们简化模型。什么模型比较好简化呢?我们想到了这题。似乎可以尝试把括号看成树的欧拉序,然后就转化为树上操作啦。
- 操作 相当于任意交换一个节点的所有子树。
- 操作 相当于将一个节点和它的所有儿子归到它兄弟的儿子上,代价与这个有关系。
- 操作的目标即得到一条链。
x=0,y=1
- 容易发现几个简单的性质:单调性:每个节点的深度不降,简单性:每次只会改变一个节点的深度。
- 直观上看 最简单,因为最终的答案只与每个节点的深度有关,算出每个点的深度,现在目标就变成了给定一个排列 ,满足 ,且最小化 ,实质是最小化 。
- 它或许不那么形象(换成树的模型或许形象很多),但是如果从大到小枚举 ,目前会挑选哪个在 层呢?一定是 最小的吧,但是有一个前提条件,那就是前 层必须保留超过 个节点,我们当然是贪心地把 目前 最大的保留,这就是一个简单的 贪心算法(让小儿子出远门),代码。
- 接下来或许就不那么简单了,但是我们或许可以对算法作一个有趣的猜测:说不定就全是贪心呢?
x=1,y=0
- 首先可以确定的是:我们完全可以维持一个循环不变的状态,即由上往下地推之后,所有其它节点都是某个节点的儿子(这样总是更有利于我们做出决策的,而且后面可以看到,这种情况下,所有可能的更优解也都循环回这样的情况),如果我们给出一个最终节点排列(首先它得合法)并宣称它是最优情况,那么我们可以贪心地算出最优转移(如果这层滞留 个节点, 个以权值最小的一个转移到下一层, 个以留在这里的权值转移到下一层),枚举所有排列,我们有一个相当简洁的 的做法
但好像没啥用。 - 我们这个时候试下考虑 的情况吧,不论如何,我们可以量化它,计算出第 层有 个节点要向下到达第 层(),不论怎么排列这个总是不变的。
- 你会发现有一些 为 (作者曾经一度以为只有 ,然后发现 这样的序列就可以打我的;脸),而有一些 非 ,而放在大于 的位置的转移贡献至少为 ,其它的贡献都可以由最小的那个数字承担,所以应该贪心地把 的位置由较大的数去填充。
- 当然,哪些较大的数字应该可以到达这里(首先应该得合法),所以我们把这整个序列划分为多个只有末尾 的连续段内部分别处理(显然连续段之间的元素无法互换),贪心的策略仍然是把 交给最大的数,滑动的时候优先以当前最小的数为梯子,复杂度 ,代码。
- 你手工模拟发现并不对劲,在一棵树上实际操作的时候你需要实现两个目标,而两者可能不能兼得:比如说下面这棵树:
- 作者目前唯一的想法就是暴力处理这种情况,因为只需要节点凑齐 个就不会出现这种情况,那么除了第一段是二叉那么后面必须要是单链,所以只剩下两种情况:
- 延伸出两条单链:这个只需要作一次决策就可以打破僵局,分类讨论即可,不过可以归纳到后面的情况处理。
- 延伸出一条单链和一个节点,可以利用如果滑动当前后缀最大值就一定要滑动到底部(否则没有效果)的性质优化到 ,对于较小值的滑动,我们发现一个简单的事实,就是此时 恒成立,所以它不滑动到最底部(存在反复被其它最小值替换的可能,但那个显然不会作为答案)也是没有办法“服务他人”的,所以最后,我们的结论是:到了真正要做出抉择的时刻(后缀最大值出现,旁边有一个更小的值的时候),你选择一条路就只能把它走到黑……所以最终得到了靠谱的做法,代码。
x=1,y=1
- 感觉要考虑两方面欸,好复杂的样子……虽然枚举所有排列依旧可以贪心……
- 然后你发现转移依靠当前最小值和后缀和,它们都要求尽量让小的放在后面,也就是模拟第一种情况的贪心即可,代码。
- 后悔了,应该先想这一个的。
总结
- 回顾整个思考的过程,感觉三个贪心都是有迹可循的,首先对于整个复杂的模型,你首先得找到一个思路将其简化,然后你要把它具体化,量化,比如说枚举一个排列然后找到它转移依靠什么,这一步之后,你可能会发现它是贪心,也可能找到了别的算法。
- 然后就是检验准确性,结合实际模型判断你的贪心在实际上是能否做出的(比如可能不能同时让两个较优的条件满足)来完善你的贪心,这是细节上的问题,它在考试的时候还是有一定难度的,因为出题人给的数据非常良心。
- 总地来说,帮助很大。
- 1
信息
- ID
- 251
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 7
- 已通过
- 2
- 上传者