能量球的最优合成策略

背景介绍

在成功协助G调整了石块与荷叶的位置后，D和Z顺利地穿过了池塘，但不幸的是，G却被大Boss捉走。大Boss拥有一种强大的武器——能量球，这种武器由多个能量珠合成。由于大Boss的能量球已经耗尽，他强迫G为其制造新的能量球。为了对抗D和Z，大Boss希望能量球尽可能强大；然而，G则希望能量球的能量值尽可能低，以便减少对D和Z的威胁。

问题描述

给定一系列的能量珠，每次可以选择两个相邻的能量珠进行合并，新生成的能量珠的能量等于这两个能量珠的能量之和。整个过程中，最终形成的大能量球的能量值定义为所有合并步骤中新生成能量珠的能量之和。G的目标是找到一种方法，使最终合成的能量球的能量值最小。

输入说明

输入包含两行：
第一行是一个整数n（1 ≤ n ≤ 200），表示能量珠的数量。
第二行包含n个整数，表示这些能量珠的能量值，首尾相连形成一个环。

输出说明

输出一个整数，即按照最优策略合成能量球后，最小可能的能量值。

解题思路

此问题可以通过动态规划的方法解决，类似于矩阵链乘法的问题。直接使用朴素的动态规划算法可能会遇到时间效率的问题，因此需要采用四边形不等式进行优化，以提高算法的执行效率。虽然理论上四边形不等式是优化的关键，但在实际操作中，使用编译器优化选项（如O2）也可能达到满意的效果。