c070. 4. 投資遊戲

Content

你擁有一個長度為 $n$ 的陣列，代表每天的投資收益，以及 $k(k≤20)$ 張金牌。

你可以自行決定投資的開始和結束日期。在你選擇投資的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。你的目標是找出如何投資，以實現最大的總收益。

請注意，你只能在投資期間進出一次。

Input

第一行包含兩個整數：$n$ 和 $k$，以空格分隔。$n$ 表示天數，$k$ 表示金牌數。

第二行包含 $n$ 個整數，以空格分隔，代表每天的投資收益。這些整數按照天數的順序給出，數值範圍為 $−10000 \sim 10000$。

子題分數：

20%：滿足 $k=0$，且 $1≤n≤2000$。
20%：滿足 $k=0$，且 $1≤n≤150000$。
60%：滿足 $1≤k≤20$，且 $1≤n≤150000$。

Output

請輸出一個整數，代表達到的最大收益。

Sample Input #1

9 0
3 1 -2 3 -2 3 -5 2 2

Sample Output #1

Sample Input #2

9 2
3 1 -2 3 -2 3 -5 2 2

Sample Output #2

Sample Input #3

9 4
3 1 -2 3 -2 3 -5 2 2

Sample Output #3

Sample Input #4

3 0
-1 -5 -3

Sample Output #4

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

Tags:

出處:

2023年10月 APCS 演算法海牛 [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」