切換
舊版
前往
大廳
主題

ZeroJudge - e332: NOIP2018 Day1.1.鋪設道路 解題心得

Not In My Back Yard | 2019-08-08 23:25:35 | 巴幣 0 | 人氣 135

題目連結:


題目大意:
給定一正整數 n (1 ≦ n ≦ 100000),代表有一段道路被分作 n 個區域,編號為 1 ~ n。接著的一列輸入有 n 個非負整數 d (0 ≦ d ≦ 10000),依序代表這 n 個區域的下陷深度。

而施工者每天可以選一段區間 [l, r] 代表使第 l ~ 第 r 個區域它們的深度減一。其中,[l, r] 中的所有區域事先都是深度 > 0 的。

求最少需要幾天,可以將這 n 個區域填補完畢(深度皆為 0 )。



範例輸入:
6
4 3 2 5 3 5


範例輸出:
9


解題思維:
以範例輸入而例,最上面一排代表總深度,下面的每個「D」一單位深度:

 3 2 5 3 5
 D D D D D
 D D D D D
 D   D D D
     D   D
      D   D
由於前面沒有任何區域,所以目前可知至少要 4 天才能填補完(因為第一個數字是 4 )。

4  2 5 3 5
D  D D D D
D  D D D D
D    D D D
D     D   D
      D   D
因為前面的區域深度為 4 ,此區域為 3 。因此還是得花至少 4 天才能填補完。

4 3  5 3 5
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  3 5
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  5
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 
D D D D D 
D D D D D 
D D   D D 
D     D   
      D   
3 < 5,因此會多上 5 - 3 天。

以上,所以最少需要 9 天才能填補完這 6 個區域。而且我們可以看出,當現在的區域之深度 > 前一區域的深度時,則最少的施工天數會增加這兩個區域深度之差值之多。

因此,當我們輸入進這 n 個數字之後,即可求得解。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作