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
并不难的贪心。