d083. Q_6_14 K次買賣 (106 高中全國賽 subtask)

Content

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

Input

第一行是正整數 n 與 K，第二行有 n 個正整數 p[1], p[2],…,p[n]。

n 不超過 1e5，K<100，商品價格皆不超過 1e7。

Output

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

Sample Input #1

5 1
3 5 1 4 0

Sample Output #1

Sample Input #2

7 2
1 3 7 5 1 4 0

Sample Output #2

測資資訊：

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

Hint ：

範例一說明：買 1 賣 4。
範例二說明：買 1 賣 7，再買 1 賣 4。
(本題有更效率更高的解法，但難度太高，這裡只要求 O(kn)的解)

Tags:

ch6

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」