Input

Output

Sample

3

5 10 3

28

这是个十分难理解的题目，一难：难理解题意； 二难：难理解算法

题意简略为：

把一些奇怪的湿蝙蝠皮夹在书中，每张蝙蝠皮都带一个值，每张蝙蝠皮的两边的书的页数不能少于这个值，求最小须要使用多少页书的书本？

非常奇怪吧，只是她是说个魔法故事的。多奇怪都不奇怪，O(∩_∩)O~

本题算法：

样例中为什么是28呢？

误解：5页+max(5,10) + max(10, 3) + 3 = 28

正解：3页+max(3, 5)+max(5, 10)+10 = 28

再看一个样例：

6

1 3 2 5 4 6

误解：1页+max(1, 3) + max(3, 2)+max(2,5)+max(5,4)+max(4,6) + 6 = 29

正解：1页+max(1, 2) +max(2, 3) + max(3, 4)+max(4,5)+max(5,6)+6 = 27

这就能够看出规律来了：

先排序然后求解。

只是这个尽管是正确解，可是最佳是：sum+max(array)

为什么要这样呢？

看清楚题意，题目没有规定要使用上面顺序来放这些蝙蝠皮，所以我们能够随便安排这些蝙蝠皮的位置--要读题读出这个意思不easy啊。

那么为什么要由小到大安排呢？

由于我们必需要保证小的数值的蝙蝠皮必需要使用到，不能保证使用两次。那就保证使用一次 -- 那么就仅仅能是由小到大安排了。

理解了意思之后，程序却是十分简单的：

#include <algorithm>

#include <iostream>

using namespace std;

void TearsofDrowned1935()

{

	int n = 0, a = 0, ans = 0, maxNum = 0;

	cin>>n;

	for (int i = 0; i < n; i++)

	{

		cin>>a;

		ans += a;

		maxNum = max(maxNum, a);

	}

	ans += maxNum;

	cout<<ans;

}