「沒有人能在我的BGM裡打敗我」是一個動漫迷因，當角色的專屬 BGM 響起，那麼無論對手多強，都已經注定了獲勝的一方。
已知有 N 場依序進行的戰鬥，第 i 場戰鬥會對你造成傷害 di。
你可以策略性地播放 BGM 來降低傷害，播放規則如下：
最多可播放 M 次，當然也可以少於 M 次BGM 歌曲長度為 L，若在第 i 場戰鬥播放，則第 i 場至第 i+L-1 場戰鬥的傷害皆會歸零；若 i+L-1 超過最後一場，則只影響至最後一場戰鬥需冷卻 C 場戰鬥，即若在第 i 場戰鬥播放，將至 i+L-1 場戰鬥時播放結束，因此下次最早只能在第 i+L+C 場戰鬥播放
請問最多可以避免的總傷害為多少？
舉例來說，
假設有 8 場戰鬥，傷害值分別為 {5, 1, 3, 10, 2, 7, 6, 4}，
最多可播放 2 次、歌曲長度為 2、每次播放結束需冷卻 1 場戰鬥。
最佳策略為於黃色標記處播放歌曲 {5, 1, 3, 10, 2, 7, 6, 4}，並避免 (3+10+7+6) = 13 的總傷害。
假設有 10 場戰鬥，傷害值分別為 {30, 30, 1, 40, 40, 1, 100, 100, 1, 1}，
最多可播放 2 次、歌曲長度為 2、每次播放結束需冷卻 2 場戰鬥。
最佳策略為於黃色標記處播放歌曲 {30, 30, 1, 40, 40, 1, 100, 100, 1, 1}，並避免 (30+30+100+100) = 260 的總傷害。
第一行有一個正整數 N，代表有 N 場戰鬥
1 ≤ N ≤ 106
第二行有 N 個非負整數 di，代表第 i 場戰鬥會造成的傷害
0 ≤ di ≤ 1000
最後一行有三個正整數 M, L, C，代表最多可播放 M 次、每次播放長度 L、兩次播放必須間隔 C 場
1 ≤ M, C ≤ 20
1 ≤ L ≤ 1000
最多可以避免的總傷害
8 5 1 3 10 2 7 6 4 2 2 1
26
10 30 30 1 40 40 1 100 100 1 1 2 2 2
260
10%：M = 1
20%：M = 2
30%：N ≤ 100
40%：無特別限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||