首先经典的结论是有很多个环，让每个环最小。
显然将数组从小到大排序，然后每个环都是取连续一段一定最优，交换法容易证明。
然后对于每个环内如何最优呢？假设我们有从小到大排序的数组 \(a_{\{1,n\}}\) ，最优一定是这样的：
\[a_1,a_3,a_5,a_7... a_8,a_6,a_4,a_2 \]就是左右填数。为什么呢？考场是打表得出。因为构造出这个方法后使用交换证明发现是最优的。
这不是这道题最傻逼的地方，前面是平凡的思维。然后不知道傻逼出题人是怎么把这个环和这个结论复合在一起的。如果往二分答案想就失败了，因为现在问题等价于把一个长度为 \(n\) 的序列分为若干段，每段价值已经处理好（\(O(n^3)\) 预处理），段的长度已经固定（环长），这个东西贪心做不了，只能使用指数级别的算法。
如果长度为 \(i\) 的环有 \(x_i\) 个，我们得到以下式子：
\[(\sum_{i=1}^n x_i\times i)=n \]然后，状态数就是：
\[\prod_{i=1}^n(x_i+1) \]这个东西最大值是 \(4230144\)，打表发现，取 \(x=\{16,8,5,3,3,2,2,1,1,1,1,1\}\) 得到。
由于转移还有常数，所以一个 \(\log\) 都不能带，所以你要建出一个 DAG，然后跑 dp，依托细节，快速处理出每个状态代表的值，乘上转移 \(12\) 的常熟就是 \(59,222,016\)，也就是常数需要优秀，最后还有记录前驱输出方案处理简直就是一坨屎，dfs 记忆化多好，一个 \(\log\) 下来只有 80pts。
出题人脑子开光出的复合题恶心人。
时间复杂度？记 \(w=59,222,016\)，时间复杂度是 \(O(w+n^3)\) 的。
标签：Vrti,59,17,Contest,18,然后,016,最优 From： https://www.cnblogs.com/g1ove/p/18519450