題目連結:
給定一正整數 n (1 ≦ n ≦ 100000),代表有一段道路被分作 n 個區域,編號為 1 ~ n。接著的一列輸入有 n 個非負整數 d (0 ≦ d ≦ 10000),依序代表這 n 個區域的下陷深度。
而施工者每天可以選一段區間 [l, r] 代表使第 l ~ 第 r 個區域它們的深度減一。其中,[l, r] 中的所有區域事先都是深度 > 0 的。
求最少需要幾天,可以將這 n 個區域填補完畢(深度皆為 0 )。
以範例輸入而例,最上面一排代表總深度,下面的每個「D」一單位深度:
4 3 2 5 3 5
D D D D D D
D D D D D D
D D D D D
D D D
D D
由於前面沒有任何區域,所以目前可知至少要 4 天才能填補完(因為第一個數字是 4 )。
4 3 2 5 3 5
D D D D D D
D D D D D D
D D D D D
D D D
D D
因為前面的區域深度為 4 ,此區域為 3 。因此還是得花至少 4 天才能填補完。
4 3 2 5 3 5
D D D D D D
D D D D D D
D D D D D
D D D
D D
同上,前一個區域深度 3 > 現在深度 2 。至少 4 天。
4 3 2 5 3 5
D D D D D D
D D D D D D
D D D D D
D D D
D D
因為現在的深度大過前一區域的深度,使得這個區域會跟前面的區域獨立。因此填補的時間會多上 5 - 2 = 3 天。因此至少 7 天。
4 3 2 5 3 5
D D D D D D
D D D D D D
D D D D D
D D D
D D
5 > 3 ,至少 7 天。
4 3 2 5 3 5
D D D D D D
D D D D D D
D D D D D
D D D
D D
3 < 5,因此會多上 5 - 3 天。
以上,所以最少需要 9 天才能填補完這 6 個區域。而且我們可以看出,當現在的區域之深度 > 前一區域的深度時,則最少的施工天數會增加這兩個區域深度之差值之多。
因此,當我們輸入進這 n 個數字之後,即可求得解。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。