题目描述

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 $N$ 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

输入格式

输入的第一行是一个正整数 $N$，表示项链上珠子的个数。

第二行是 $N$ 个用空格隔开的正整数，所有的数均不超过 $1000$，第 $i$ 个数为第 $i$ 颗珠子的头标记，当 $i<N$ 时，第 $i$ 颗珠子的尾标记应该等于第 $i+1$ 颗珠子的头标记，第 $N$ 颗珠子的尾标记应该等于第 $1$ 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

输出只有一行，是一个正整数 $E$，为一个最优聚合顺序所释放的总能量。

样例

4
2 3 5 10

710

样例解释

珠子的头标记与尾标记

• 珠子 1：头标记 2，尾标记 3（因为下一颗珠子头标记为 3）
• 珠子 2：头标记 3，尾标记 5
• 珠子 3：头标记 5，尾标记 10
• 珠子 4：头标记 10，尾标记 2（因为项链是环形的，第 4 颗珠子的尾标记应等于第 1 颗珠子的头标记 2）

因此，珠子序列为：$(2,3), (3,5), (5,10), (10,2)$。

最优聚合顺序

一种最优聚合顺序：$(4 \oplus 1) \oplus 2) \oplus 3$。

计算过程：

1. 先合并珠子 4 和珠子 1：
   $m=10$（珠子4头），$r=2$（珠子1头，也是珠子4尾），$n=3$（珠子1尾）
   能量 $= 10 \times 2 \times 3 = 60$
   新珠子头标记 10，尾标记 3（相当于 $(10,3)$）。

   此时项链变为：$(10,3), (3,5), (5,10)$（顺序是 $(10,3)$ 接 $(3,5)$ 接 $(5,10)$）。

2. 再合并新珠子 $(10,3)$ 和 $(3,5)$：
   $m=10$，$r=3$，$n=5$
   能量 $= 10 \times 3 \times 5 = 150$
   新珠子头标记 10，尾标记 5（即 $(10,5)$）。

   此时项链变为：$(10,5), (5,10)$。

3. 最后合并 $(10,5)$ 和 $(5,10)$：
   $m=10$，$r=5$，$n=10$
   能量 $= 10 \times 5 \times 10 = 500$

总能量 $= 60 + 150 + 500 = 710$。

数据范围

• $4 \le N \le 100$
• $1 \le E \le 2.1 \times 10^9$

算法分析

这是一个环形区间 DP 问题，类似于石子合并。

问题转化

由于项链是环形的，我们可以将链复制一倍，转化为长度为 $2N$ 的链，然后在上面做区间 DP。

定义珠子 $i$ 的头标记为 $a[i]$，尾标记为 $a[i+1]$（当 $i = N$ 时，尾标记为 $a[1]$）。

在复制后的链上，珠子 $i$ 的头标记为 $a[i]$，尾标记为 $a[i+1]$，其中 $a[N+1] = a[1]$，$a[N+2] = a[2]$，等等。

状态定义

设 $dp[l][r]$ 表示合并区间 $[l, r]$ 内的珠子（即 $l$ 到 $r$ 这些珠子合并成一个珠子）所能获得的最大总能量。

区间长度 $len$ 从 $2$ 开始（至少两颗珠子才能合并），到 $N$ 结束（最后合并成一顆）。

转移方程

在区间 $[l, r]$ 中，考虑最后一次合并是在哪个位置 $k$ 将 $[l, k]$ 和 $[k+1, r]$ 合并。

合并时：

• 左区间 $[l, k]$ 合并成一个珠子，头标记为 $a[l]$，尾标记为 $a[k+1]$。
• 右区间 $[k+1, r]$ 合并成一个珠子，头标记为 $a[k+1]$，尾标记为 $a[r+1]$。
• 合并这两个珠子释放的能量为 $a[l] \times a[k+1] \times a[r+1]$。

因此：

$$dp[l][r] = \max_{l \le k < r} \{ dp[l][k] + dp[k+1][r] + a[l] \times a[k+1] \times a[r+1] \}$$

环形处理

将原数组 $a[1..N]$ 复制一份到 $a[N+1..2N]$，然后对每个起点 $i$（$1 \le i \le N$）计算 $dp[i][i+N-1]$ 的最大值。

初始化

$dp[i][i] = 0$（单独一个珠子没有合并操作）。

答案

$\max_{i=1}^{N} dp[i][i+N-1]$

复杂度

• 状态数 $O(N^2)$
• 转移 $O(N)$
• 总复杂度 $O(N^3)$，$N \le 100$，可以通过。

实现细节

• 注意数组大小开 $2N$。
• 注意 $a[r+1]$ 的边界，当 $r = 2N$ 时，$a[2N+1]$ 应取 $a[1]$，但因为我们只用到 $r \le i+N-1$ 且 $i \le N$，所以 $r+1 \le i+N \le 2N$，不会越界。
• 由于是环形，复制后长度 $2N$，但实际有效区间长度不超过 $N$。

样例验证

对于样例 $N=4$，$a=[2,3,5,10]$，复制后 $a=[2,3,5,10,2,3,5,10]$。

计算 $dp[1][4]$（对应原环的起点1）：

• 区间 $[1,4]$ 的最大值即为 $710$。