#P4805. [CCC2016] 合并饭团

[CCC2016] 合并饭团

题目描述

译自 CCC2016 Senior T4「Combining Riceballs

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

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

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

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

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

输入格式

第一行,一个整数 N(1N400)N(1 \le N \le 400)

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

输出格式

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

7
47 12 12 3 9 9 3
48
4
1 2 3 1
3

提示

样例解释 1

有一种可能的合并方案为:合并大小同为 1212 的两个饭团,得到一个大小为 2424 的饭团。然后合并大小同为 99 的两个饭团,得到一个大小为 1818。接着合并大小为 3,183,1833 的三个饭团,得到一个大小为 2424 的饭团。最后合并大小同为 2424 的两个饭团,得到一个大小为 4848 的饭团。

样例解释 2

我们无法进行操作,所以答案为 33

对于 115\frac1{15} 的数据,N=4N = 4

对于另外 215\frac2{15} 的数据,N10N \le 10

对于另外 515\frac5{15} 的数据,N50N \le 50