台灣近年來經常豪雨成災。每遇有豪雨,新聞記者就將以往降雨紀錄拿出,並以聳動字眼云之,如「30 年來最大降雨量」、「40 年來首見」等。李先生是一位科學家,認為用直覺讀取數據容易造成偏頗,他想用更科學的方式來解讀降雨量,希望能找出降雨量長期趨勢。在觀察一連串的降雨量數據後,李先生想找出最長的遞增序列,以代表長期趨勢。在他所找到的長期趨勢資料中,一般而言是逐步上升,但某次破紀錄的最大雨量之後,若有稍大雨量 (雖未破紀錄),亦視為遞增序列之內容。換言之,他欲找出最長近乎遞增序列。
舉例來說,李先生的雨量數據有12 個,如下:'
9, 15, 3, 14, 14, 8, 10, 11, 17, 15, 14, 13
另外設定一個 E 值,代表稍大雨量與長期趨勢目前最大雨量可以允許的差值。假設 E = 1,則可以找出下列五組最長近乎遞增序列,其長度均為 6 :
(9, 15, 14, 14, 15, 14), (9, 8, 10, 11, 15, 14), (3, 8, 10, 11, 15, 14), (9, 8, 10, 11, 14, 13), (3, 8, 10, 11, 14, 13)
又若 E = 0,則最長近乎遞增序列有四組 (3, 8, 10, 11, 13), (3, 8, 10, 11, 14), (3, 8, 10, 11, 15), (3, 8, 10, 11, 17),其長度均為 5 。
再看另一個例子,假設雨量數據為 3, 4, 4, 6, 5, 4。若 E = 0,則有三組最長近乎遞增序列:(3, 4, 4, 6) , (3, 4, 4, 5), (3, 4, 4, 4),長度均為 4。若 E = l,則有二組:(3, 4, 4, 6, 5), (3, 4, 4, 5, 4)。若 E = 2,則有一組:(3, 4, 4, 6, 5, 4)。本題的答案只要輸出長度即可。
輸入範例 1: 12 3 9 15 3 14 14 8 10 11 17 15 14 13 0 1 999990 輸入範例 2: 4 3 1 0 999900 999800 1000 0 l
輸出範例 1: 5 6 12 輸出範例2 : 4 2 3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|