T1 Bug
题目描述
A 君在机缘巧合下得到了一把养蛊神器，于是 A 君希望培养出迄今为止战斗力最强的 Bug。A 君把现有的 \(n\) 个 Bug 排成一个序列 \(a_1, a_2, \dots, a_n\)，其中 \(a_i\) 表示第 \(i\) 个 Bug 的战斗力。A 君需要重复进行以下操作直到只剩下一个 Bug：
- 选择一个端点（指最左边或者最右边）的 Bug，删除它。
- 选择一个非端点的 Bug，将它的战斗力变为当前它左右两个相邻 Bug 的战斗力之和，然后删除左右两边的 Bug。
求操作结束后剩下的一个 Bug 的最高战斗力是多少，并求出需要的最少操作数。
输入格式
第一行一个整数，表示 \(n\)。
第二行 \(n\) 个整数，第 \(i\) 个整数表示 \(a_i\)。
输出格式
第一行一个整数，表示操作结束后剩下的 Bug 的最高战斗力。
第二行一个整数，表示需要的最少操作数。
输入输出样例 #1
输入 #1
6
-1 5 2 -2 3 -3
输出 #1
5
4
输入输出样例 #2
输入 #2
4
-2 -4 -1 -3
输出 #2
-1
3
输入输出样例 #3
输入 #3
10
32644 -36604 -178874 -98683 92567 -272835 -35544 -151678 -8486 -197803
输出 #3
125211
5
数据规模与约定
| 测试点 | \(n\le\) | 分值 |
|---|---|---|
| \(1\sim 2\) | \(10\) | \(10\) |
| \(3\sim 6\) | \(2000\) | \(20\) |
| \(7\sim 20\) | \(10^6\) | \(70\) |
对于 \(100\%\) 的数据，满足 \(-10^{10}\le a_i\le 10^{10}\)。
Sol
并不难的贪心。