Timus 1935. Tears of Drowned 詳解

Old Captain Jack Sparrow’s friend Tia Dalma, the fortuneteller and prophetess, often makes potions. She has an outstanding collection of the rarest ingredients such as rat tails, fingers of drowned, tears of virgins and so on. And all these ingredients require special care. Recently Tia Dalma received some good skins of bats as a payment, and now she wants to dry them. To dry ingredients fortuneteller usually uses specially prepared books as the magical properties of the skins could be lost during prolonged contact with other objects. Tia Dalma knows how many sheets should be on both sides of the skin to save it unspoiled. For a i-th skin that number is ai, that is, the distance from it to the neighboring skins and the book cover can’t be less than ai sheets. Help a fortuneteller determine the minimum number of sheets that should be in the book to save rare ingredients from damage.

Input

The first line contains integer n that is the number of skins (1 ≤ n ≤ 100). The second line contains n integers ai (1 ≤ ai ≤ 100).

Output

Output the minimal required number of sheets in the book.

Sample

input output

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)

為什麼要這樣呢？

看清楚題意，題目沒有規定要使用上面順序來放這些蝙蝠皮，所以我們可以隨便安排這些蝙蝠皮的位置--要讀題讀出這個意思不容易啊。

那麼為什麼要由小到大安排呢？

因為我們必須要保證小的數值的蝙蝠皮必須要使用到，不能保證使用兩次，那就保證使用一次 -- 那麼就只能是由小到大安排了。

理解了意思之後，程序卻是十分簡單的：

#include 
#include 
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<