d085: Q-6-14. K 次買賣 (106 高中全國賽 subtask)
Tags : DP
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

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
// 2
7 2
1 3 7 5 1 4 0
Sample Output
// 1
3
// 2
9
測資資訊:
記憶體限制: 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
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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