TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

74.0% (37/50)

Submission's AC Ratio

16.4% (95/581)

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

No. Testdata Range Score
1 0~5 13
2 6~13 24
3 14~21 45
4 22~30 18

Testdata and Limits

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