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$ 个点，每个点都有一个评分参数，你需要构造一个权值尽可能大的排列让权值大于评分参数。

$1\leqslant n\leqslant 1000$。

分析

不愧是黑暗森林，你永远不知道什么时候会被一道大毒瘤题坑害。/cy

考虑随机化（这貌似不是完全的遗传算法），令排列 $p$ 为基因，令上面式子的值为一个基因的优异程度，令交换任意两个数为一次变异。

我们一开始随机生成若干个基因，每次一个基因诞生若干个后代，然后将后代按优异程度排序，删除部分不优秀的后代使得后代数量控制在一个范围内。然后每次再给最优秀的族群产生一个新的后代，并爬山得到较优的解。

然后就耐心跑吧，实在不行调调参，反正我一晚上就跑出来两个包。

也可以尝试加一些特判，比如如果陷入一个局部最优解就强行让部分后代变异若干次，然后改变一次生存法则之类的，这样应该会好一点。

我竟然跑出来了，难以置信。

代码不放了，想要私信。