题解 P7812【[JRKSJ R2] Dark Forest】

· · 题解

P7812 [JRKSJ R2] Dark Forest解题报告：

更好的阅读体验

题意

给定一个长度为 n 的序列 a，定义一个排列 p 的权值为 \sum_{i=1}^np_ia_{p_{i-1}}a_{p_i}a_{p_{i+1}}。

一共有 10 个点，每个点都有一个评分参数，你需要构造一个权值尽可能大的排列让权值大于评分参数。

## 分析 不愧是黑暗森林，你永远不知道什么时候会被一道大毒瘤题坑害。/cy 考虑随机化（这貌似不是完全的遗传算法），令排列 $p$ 为基因，令上面式子的值为一个基因的优异程度，令交换任意两个数为一次变异。 我们一开始随机生成若干个基因，每次一个基因诞生若干个后代，然后将后代按优异程度排序，删除部分不优秀的后代使得后代数量控制在一个范围内。然后每次再给最优秀的族群产生一个新的后代，并爬山得到较优的解。 然后就耐心跑吧，实在不行调调参，反正我一晚上就跑出来两个包。 也可以尝试加一些特判，比如如果陷入一个局部最优解就强行让部分后代变异若干次，然后改变一次生存法则之类的，这样应该会好一点。 我竟然跑出来了，难以置信。 代码不放了，想要私信。