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

範例輸入 #2

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

範例輸出 #2

範例輸入 #3

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

範例輸出 #3

範例輸入 #4

3 0
-1 -5 -3

範例輸出 #4

測資資訊：

記憶體限制： 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

提示：

標籤:

出處:

2023年10月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
38135	xx0932399@gm ... (Dada878)	m373	✅ 1 ~ 4 題實做考點分析 x 解題思路 x 詳細解法	1647	2023-10-29 16:16
40639	willychan100 ... (詹哲崴)	m373	你說的對，但是SMAWK	1883	2024-06-03 15:08
40958	glps1004@gma ... (Ian)	m373	APCS 202310全部解析	222	2024-06-21 18:11
40651	john1100729@ ... (靖諺)	m373	C++ 詳解	456	2024-06-03 20:36
38059	Bangye (風清揚)	m373	APCS 2023.10實作題C++與Python題解	938	2023-10-23 18:07