← 返回题目
题库练习 消消乐
← 上一题 下一题 →

A72040 | 消消乐

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一个由 n 个整数构成的数组 a=[a_1,\ldots,a_n]。每次你可以对数组 a 进行以下操作，直到数组 a 变为空：

指定 a 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 a 中删去。特别地，如果相邻元素不存在则该元素的值视为 0。

请问你能获得的分数总和最大是多少？

输入格式

第一行，一个正整数 n，表示数组长度。

第二行，n 个非负整数 a_1,\ldots,a_n，表示数组 a 中的整数。

输出格式

输出一行，一个整数，表示能获得的最大分数总和。

输入输出样例

输入 #1
6
1 6 3 2 9 1
输出 #1
55
输入 #2
5
3 1415 926 53 58
输出 #2
5771
C++ 编辑器
输入
输出