748 . 柵欄粉刷

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

25.0% (1/4)

Tags

apcsc apcsc-dc

Description

小普正在油漆行打工，今天他的任務是粉刷柵欄，柵欄由 $N$ 個寬度為一單位的柱子排成一列所組成，由左往右數來第 $i$ 根柱子的高度是 $a_i$ 單位。
由於小普是個細心的油漆工，而他的油漆刷寬度剛好也是一單位，他規定自己每次只能橫向粉刷一排柵欄或著垂直粉刷一根柵欄，而且單次粉刷過程中，油漆刷都不能離開柵欄表面。
舉例來說，假設組成柵欄的柱子高度依序為 2 2 1 2 1，則其中一種粉刷方式為先橫向粉刷所有柵欄的第一層，再橫向粉刷第 $1$ 、 $2$ 根柵欄的第二層，最後在粉刷剩下的第 $4$ 根柵欄的第二層，總共需要 $3$ 次粉刷。
小普希望能在滿足規定的前提下盡早回家，聰明如你能幫小普算出最少需要幾次粉刷，才能將整個柵欄都粉刷過一遍呢？

Input Format

輸入第一行為一個正整數 $N (1 \leq N \leq 100000)$，代表柵欄的寬度。
輸入第二行包含 $N$ 個用空白分隔的正整數 $a_i (1 \leq a_i \leq 10^ 9)$，代表由左往右數來第 $i$ 根柱子的高度。

Output Format

輸出一個整數，代表最少需要幾次粉刷，才能將整個柵欄都粉刷過一遍。

Sample Input 1

5
2 2 1 2 1

Sample Output 1

3

Sample Input 2

2
2 2

Sample Output 2

2

Sample Input 3

1
5

Sample Output 3

1

Hints

Problem Source

Codeforces Round #256 (Div. 2) C. Painting Fence

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
Submit
Back to Top