e332: NOIP2018 Day1.1.铺设道路
Tags :
Accepted rate : 16人/19人 ( 84% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-22 16:21

Content

春春是一名道路工程师,负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di

春春每天可以选择一段连续区间 [L,R] ,填充这段区间中的每块区域,让其下陷深度减少1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 。

春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为0。

Input

输入包含两行,第一行包含一个整数 n,表示道路的长度。 第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。

Output

输出文件仅包含一个整数,即最少需要多少天才能完成任务。

Sample Input
6
4 3 2 5 3 5
Sample Output
9
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :

对于30%的数据,1≤n≤10;

对于70%的数据,1≤n≤1000;

对于100%的数据,1≤n≤100000,0≤di≤10000 .

Tags:
出處:
NOIP2018提高组Day1第一题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」