#1931. 分发蛋糕

分发蛋糕

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

打开宝箱后,小Z欣喜若狂,这不就是他梦寐以求的机械键盘吗,他太开心了,他要跟小伙伴们分享今天的喜悦,他决定邀请今天帮助过他的小伙伴举行欢庆会,他打算为这些小伙伴们准备一些蛋糕,n\red{n}个小伙伴站成一排,每个小伙伴都有一个贡献值ai\red{ai},也就是今天对他的帮助程度,他将按照一下规则,对小伙伴进行分发蛋糕:

1)每个小伙伴至少分到1\red{1}个蛋糕

2)相邻的两个小伙伴贡献值更高\red{贡献值更高}的会获得更多的蛋糕

你能够帮他算一下最少\red{最少}需要多少块蛋糕吗?

输入格式

n+1\red{n+1}

第一行一个正整数n\red{n}表示参加庆功会的小伙伴的人数

第二行为n\red{n}个数分别表示每个人的贡献值,用空格隔开

输出格式

共一行为一个正整数s\red{s},表示最少的蛋糕数

样例

输入数据1

3
1 0 2

输出数据1

5

输入数据2

3
1 2 2

输出数据2

4

提示

数据范围与提示

对于输入样例1\red{输入样例1},贡献值分别为102\red{1 , 0 ,2}

由于每个孩子至少有一块蛋糕,所以三个人出示蛋糕数为111\red{1 ,1 , 1}

第一个人的贡献值大于第二个人,所以一个人的蛋糕数会比第二人多,最少为2\red{2}块。第二个人比相邻人都小,故第二人为1\red{1}块蛋糕,第三人比第二人贡献值大,所以第三人的蛋糕数比第二人多,最小为2\red{2}块。

分别给第一个、第二个、第三个孩子分发212\red{2、1、2} 块蛋糕。

对于 20%\red{20\%}的数据1<=n<=100,0<=ai<=100\red{1 <= n <= 100, 0<=ai<=100}

对于50%\red{50\%}的数据1<=n<=1000,0<=ai<=1000\red{1 <= n <= 1000, 0<=ai<=1000}

对于100%\red{100\%}的数据1<=n<=20000,0<=ai<=20000\red{1 <= n <= 20000, 0<=ai<=20000}

2022年小云雀c++小学组重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-4-10 16:00
结束于
2023-4-11 22:00
持续时间
30 小时
主持人
参赛人数
304