a348. Q-6-14. K次買賣 (106高中全國賽subtask)

內容

某商品在某個時期每一天的價格是p[1], p[2],…,p[n]。假設只能先買後賣，且賣了之後才能再買，請計算買賣K次的最大獲利總價差，允許當天買賣，也就是不超過K次的買賣。

輸入說明

第一行是正整數n與K，第二行有n個正整數p[1], p[2],…,p[n]。n不超過1e5，K<100，商品價格皆不超過1e7。

輸出說明

買賣不超過K次的最大總價差。

範例輸入 #1

5 1
3 5 1 4 0

範例輸出 #1

範例輸入 #2

7 2
1 3 7 5 1 4 0

範例輸出 #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

範例一說明：買1賣4。
範例二說明：買1賣7，再買1賣4。

標籤:

出處:

AP325 [管理者：

haha (大學長)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」