题目名称：合并饭团
题目ID：20065
题目描述
题目描述
Alphonse 有 N 个美味的饭团，它们大小不一，摆放成一行。他想把最大的饭团让给自己的基友。他可以执行以下操作：
如果两个相邻的饭团大小相同，Alphonse 可以把它们合并成一个新的饭团。新饭团的大小是两个原饭团大小之和。它将占据两个原饭团先前占据的位置。
如果两个饭团大小相同，且它们之间只有一个饭团，Alphonse 也可以把它们合并成一个新的饭团。（中间的饭团大小没有规定。）新饭团的大小是三个原饭团大小之和，并占据三个原饭团先前的位置。
Alphonse 可以按照他的意愿执行任意次操作。
在执行 0 或更多次操作后，确定他应该把哪个饭团让给基友。
输入格式
第一行，一个整数 N(1≤N≤400)。
第二行，N 个以空格分隔的整数，表示每个饭团的大小，按照从左到右的顺序给出。每个整数的上界为 1 000 000。
输出格式
输出 Alphonse 可以得到的最大的饭团大小。
样例 #1
样例输入 #1
7
47 12 12 3 9 9 3
样例输出 #1
48
样例 #2
样例输入 #2
4
1 2 3 1
样例输出 #2
3
提示
样例解释 1
有一种可能的合并方案为：合并大小同为 12 的两个饭团，得到一个大小为 24 的饭团。然后合并大小同为 9 的两个饭团，得到一个大小为 18。接着合并大小为3,18 和 3 的三个饭团，得到一个大小为 24 的饭团。最后合并大小同为 24 的两个饭团，得到一个大小为 48 的饭团。
样例解释 2
我们无法进行操作，所以答案为 3。
对于 100% 的数据，N≤400。
一看题目就知道是 dp 。
但是输出数列中的最大值能 {\color{Green} AC} !
事后…
2025/2/6，16:07左右，数据加强，将样例1作为了Test1，样例2也改了，100分成了80分。