TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

68.8% (11/16)

Submission's AC Ratio

31.7% (45/142)

Description

商品價格經常是起起伏伏,例如石油的價格幾乎時時都有變動,有時上漲,有時下跌。商品交易商在低價時買進高價賣出就可以利用其中的價差獲取利益。2066 年6 月6 日Automatic Investment 公司以複雜的人工智慧技術開發一套商品價格的預測系統,此系統命名為AI-666,但發展了這麼多複雜的運算技術後,他們現在剩下一個小問題:假設AI-666 的價格預測是準確的,那麼最多可以在這一段期間賺到多少錢。公司的研發經理希望以這個問題來考驗你,看看你是否有資格加入該公司的研發團隊。

商品交易的規則是這樣的:
1. 只能先買後賣,不可以先賣後買。
2. 每次買與賣都限定是一個單位的商品。同時,在買入之後,賣出之前,不可以再買入。
3. 由於法令的規定,在此期間內最多只能進行K 次的交易(一次交易包含買賣各一次)。

輸入的資料是AI-666 系統所預測$N$ 個時間點的商品價格以及一個正整數$K$,請計算不超過$K$ 次交易的條件下最大可能獲得的利益。
舉例來說,以下資料是11 個時間點的價格:

如果$K=1$,最大的獲利方式是$80$ 買進,$180$ 賣出,可以獲利$100$。如果$K=2$,最大獲利方式是$90$ 買進,$185$ 賣出,然後$80$ 再買進,$180$ 賣出,總共可以獲利$95+100=195$。如果$K=5$,雖然可以交易五次,但交易四次就可以達到最大獲利$(185-90)+(150-80)+(180-140)+(150-110)=245$。

Input Format

每筆測資共有二行。第一行為兩個正整數$N$ 與$K$,分別代表時間點數與交易次數上限,其中$N>1$。第二行有$N$ 個以空白間隔的正整數,依序是各時間點的價格。每一價格均為不超過$10000000$ 的正整數,每筆測資的最大可能獲利不超過$1500000000$。

Output Format

以單獨一行輸出不超過K 次交易的最大可能獲利,若無法獲利則應輸出0。

Sample Input

Sample Input #1
11 1
100 90 185 120 80 150 140 180 110 150 50

Sample Input #2
11 2
100 90 185 120 80 150 140 180 110 150 50

Sample Input #3
11 5
100 90 185 120 80 150 140 180 110 150 50

Sample Input #4
3 1
100 100 85

Sample Output

Sample Output #1
100

Sample Output #2
195

Sample Output #3
245

Sample Output #4
0

Hints

本題共有四個子題,每一子題可有多筆測試資料,全部解出可獲該子題的分數。
第一子題(13 分):$N \leq 1000, K =1$。
第二子題(24 分):$N \leq 50000, K \leq 100$。
第三子題(45 分):$N \leq 200000,K \leq N$。
第四子題(18 分):$N \leq 2000000,K \leq N$。

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第六題

Subtasks

For Testdata: 0 ~ 5, Score: 13
For Testdata: 6 ~ 13, Score: 24
For Testdata: 14 ~ 21, Score: 45
For Testdata: 22 ~ 30, Score: 18
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 666 524288 65536
1 666 524288 65536
2 666 524288 65536
3 666 524288 65536
4 666 524288 65536
5 666 524288 65536
6 666 524288 65536
7 666 524288 65536
8 666 524288 65536
9 666 524288 65536
10 666 524288 65536
11 666 524288 65536
12 666 524288 65536
13 666 524288 65536
14 666 524288 65536
15 666 524288 65536
16 666 524288 65536
17 666 524288 65536
18 666 524288 65536
19 666 524288 65536
20 666 524288 65536
21 666 524288 65536
22 666 524288 65536
23 666 524288 65536
24 666 524288 65536
25 666 524288 65536
26 666 524288 65536
27 666 524288 65536
28 666 524288 65536
29 666 524288 65536
30 666 524288 65536