合并饭团(Combining Riceballs)

题目描述

Alphonse 有 $N$ 个美味的饭团，它们大小不一，摆放成一行。他想把最大的饭团让给自己的基友。他可以执行以下操作：

• 如果两个相邻的饭团大小相同，Alphonse 可以把它们合并成一个新的饭团。新饭团的大小是两个原饭团大小之和。它将占据两个原饭团先前占据的位置。

• 如果两个饭团大小相同，且它们之间只有一个饭团，Alphonse 也可以把它们合并成一个新的饭团。（中间的饭团大小没有规定。）新饭团的大小是三个原饭团大小之和，并占据三个原饭团先前的位置。

Alphonse 可以按照他的意愿执行任意次操作。

在执行 0 或更多次操作后，确定他应该把哪个饭团让给基友。

输入格式

第一行，一个整数 $N(1 \le N \le 400)$。

第二行，$N$ 个以空格分隔的正整数，表示每个饭团的大小，按照从左到右的顺序给出。每个正整数的上界为 $1\ 000\ 000$。

输出格式

输出 Alphonse 可以得到的最大的饭团大小。

样例输入 #1

7
47 12 12 3 9 9 3

样例输出 #1

48

样例输入 #2

4
1 2 3 1

样例输出 #2

3

数据范围

样例解释 1

有一种可能的合并方案为：合并大小同为 $12$ 的两个饭团，得到一个大小为 $24$ 的饭团。然后合并大小同为 $9$ 的两个饭团，得到一个大小为 $18$。接着合并大小为 $3,18$ 和 $3$ 的三个饭团，得到一个大小为 $24$ 的饭团。最后合并大小同为 $24$ 的两个饭团，得到一个大小为 $48$ 的饭团。

样例解释 2

我们无法进行操作，所以答案为 $3$。

对于 $\frac1{15}$ 的数据，$N = 4$。

对于另外 $\frac2{15}$ 的数据，$N \le 10$。

对于另外 $\frac5{15}$ 的数据，$N \le 50$。

对于 $100\%$ 的数据，$1 \le N \le 400$，每个饭团大小不超过 $10^6$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1750。

测试点分布

出处：原题链接