m373. 4. 投資遊戲
Tags :
Accepted rate : 370人/529人 ( 70% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-10-22 21:36

Content

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

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

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

 

Input

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

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

 

子題分數:

  • 20%:滿足 $k=0$,且 $1 \leq n \leq 2000$。
  • 20%:滿足 $k=0$,且 $1 \leq n \leq 150000$。
  • 60%:滿足 $1 \leq k \leq 20$,且 $1 \leq n \leq 150000$。
Output

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

Sample Input #1
9 0
3 1 -2 3 -2 3 -5 2 2
Sample Output #1
6
Sample Input #2
9 2
3 1 -2 3 -2 3 -5 2 2
Sample Output #2
12
Sample Input #3
9 4
3 1 -2 3 -2 3 -5 2 2
Sample Output #3
14
Sample Input #4
3 0
-1 -5 -3
Sample Output #4
0
測資資訊:
記憶體限制: 256 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 [管理者: algo.seacow@ ... (演算法海牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
38135 xx0932399@gm ... (Dada878) m373
1308 2023-10-29 16:16
40639 willychan100 ... (詹哲崴) m373
554 2024-06-03 15:08
40958 glps1004@gma ... (Ian) m373
34 2024-06-21 18:11
40651 john1100729@ ... (靖諺) m373
C++ 詳解
198 2024-06-03 20:36
38059 Bangye (風清揚) m373
740 2023-10-23 18:07