m373. 4. 投資遊戲
標籤 :
通過比率 : 439人/605人 ( 73% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

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

 

輸入說明

第一行包含兩個整數:$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$。
輸出說明

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

範例輸入 #1
9 0
3 1 -2 3 -2 3 -5 2 2
範例輸出 #1
6
範例輸入 #2
9 2
3 1 -2 3 -2 3 -5 2 2
範例輸出 #2
12
範例輸入 #3
9 4
3 1 -2 3 -2 3 -5 2 2
範例輸出 #3
14
範例輸入 #4
3 0
-1 -5 -3
範例輸出 #4
0
測資資訊:
記憶體限制: 256 MB
提示 :
標籤:
出處:
2023年10月APCS [管理者: algo.seacow@ ... (演算法海牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
38135 xx0932399@gm ... (Dada878) m373
1549 2023-10-29 16:16
40639 willychan100 ... (詹哲崴) m373
1792 2024-06-03 15:08
40958 glps1004@gma ... (Ian) m373
163 2024-06-21 18:11
40651 john1100729@ ... (靖諺) m373
C++ 詳解
376 2024-06-03 20:36
38059 Bangye (風清揚) m373
879 2023-10-23 18:07