小明在經過區賽的廝殺後，終於晉級夢寐以求的全國賽了！為了在全國賽當天能夠以最好的狀態上場，小明與他的朋友一共 n 個人在比賽會場附近訂了一間 n 人房，以養精蓄銳一番。
當他們進了房，鋪好床要設定鬧鐘時，突然發現一個問題：每個人想起床的時間都不一樣，但是每個人如果都設定自己的鬧鐘，早響起的鬧鐘勢必會吵醒晚起的人，而每個人都希望自己的睡眠時間愈長愈好。
經過一番調查後，他們發現其中第 i 個人想要起床的時間在第 ai 分鐘後，會睡在由左至右第 i 張床上。而他們的鬧鐘的影響範圍是 k，也就是說，如果第 x 個人設置的鬧鐘響起，則第 x − k 個人到第 x + k 個人都會起來。
他們可以設定任意多個鬧鐘，設定在任何時間點響起，但是需要滿足一些條件。假設他們一共設置了 m 個鬧鐘，第 j 個鬧鐘由第 bj 個人設置，在第 cj 分鐘後響起，則需要滿足以下條件：
1. 為了避免吵到其他寢室的人們，第 1 到第 k、第 n - k + 1 到第 n 個人都不能設置鬧鐘。也就是說對於所有 1 ≤ j ≤ m，k + 1 ≤ bj ≤ n−k。
2. 每個人至少要被一個鬧鐘叫醒。也就是說對於所有 1 ≤ i ≤ n，至少存在一個 j 滿足 i−k ≤ bj ≤ i + k。
3. 每個人在被一個鬧鐘叫醒後，就不會再入睡。此時他起來的時間點不能在第 ai 分鐘後。也就是說，對於所有 1 ≤ i ≤ n ，令 P 為所有滿足 i - k ≤ bj ≤ i + k 的 j 中，cj 的最小值。則需滿足 P ≤ ai，其中 P 就是第 i 個人會起來的時間點。
舉例來說,如果有 n = 5 個人，鬧鐘的影響範圍是 k = 1，他們起來的時間點分別是 a = [3, 1, 2, 5, 4]。注意到在這種情形下，第 1 個人與第 5 個人不能設定鬧鐘。考慮以下三種情形：
1. 如果第 2 個人設定鬧鐘在第 1 分鐘響，第 4 個人設定鬧鐘在第 4 分鐘響，則他們起來的時間會是 [1, 1, 1, 4, 4]，符合鬧鐘的設置條件，睡的長度時間總和是 1+1+1+4+4 = 11。
2. 如果第 2 個人設定鬧鐘在第 1 分鐘響，第 3 個人設定鬧鐘在第 4 分鐘響，則不符合鬧鐘的設置條件，因為第 5 個人不會被任何鬧鐘叫醒。
3. 如果第 2 個人設定鬧鐘在第 1 分鐘響，第 4 個人設定鬧鐘在第 5 分鐘響，也不符合鬧鐘的設置條件，因為他們起來的時間點分別為 [1, 1, 1, 5, 5]，第 5 個人起來的時間點超過 a5 = 4。
請問如果適當的設置鬧鐘,他們能睡的長度時間總和最大可以是多少?
每筆測資的輸入共有兩行。
第一行有兩個整數 n, k，代表寢室的人數及鬧鐘的影響範圍大小。
接下來的一行包含 n 個正整數 a1 ∼ an，代表第 i 個人最多還能再睡 ai 分鐘。
1. k ≥ 0。
2. 2*k + 1 ≤ n。
3. 1 ≤ ai ≤ 500000。
輸出一個正整數於一行，代表如果適當的設置鬧鐘，能睡的長度時間總和最大可以是多少。
#test input 1: 5 1 3 1 2 5 4 #test input 2: 1 0 12 #test input 3: 16 3 10 2 17 26 2 23 31 13 9 21 4 4 12 13 19 10
#test output 1: 11 #test output 2: 12 #test output 3: 80
dp, greedy (CF 2800)
7% 的測資滿足 1 ≤ n ≤ 3000，對於所有滿足 1 ≤ i < n 的 i ，ai ≤ ai+1。
14% 的測資滿足 1 ≤ n ≤ 3000，對於所有滿足 1 ≤ i ≤ n 的 i ，ai = 1 或 2。
16% 的測資滿足 1 ≤ n ≤ 100。
24% 的測資滿足 1 ≤ n ≤ 500。
39% 的測資滿足 1 ≤ n ≤ 3000。
//如果你 dp 真的很強，可以試試這一題
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||