m373.
4. 投資遊戲
內容
你擁有一個長度為 $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
公開 測資點#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
公開 測資點#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
提示 ：
標籤:
出處:
2023年10月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 38135 |
|
m373 | 1519 | 2023-10-29 16:16 | |
| 40639 |
|
m373 | 1749 | 2024-06-03 15:08 | |
| 40958 |
|
m373 | 140 | 2024-06-21 18:11 | |
| 40651 |
|
m373 | 334 | 2024-06-03 20:36 | |
| 38059 | Bangye (風清揚) | m373 | 858 | 2023-10-23 18:07 |