商品價格經常是起起伏伏，例如石油的價格幾乎時時都有變動，有時上漲，有時下跌。
商品交易商在低價時買進高價賣出就可以利用其中的價差獲取利益。2066 年6 月6 日
Automatic Investment 公司以複雜的人工智慧技術開發一套商品價格的預測系統，此系統命名
為AI-666，但發展了這麼多複雜的運算技術後，他們現在剩下一個小問題：假設AI-666 的價
格預測是準確的，那麼最多可以在這一段期間賺到多少錢。公司的研發經理希望以這個問題
來考驗你，看看你是否有資格加入該公司的研發團隊。
商品交易的規則是這樣的：
• 只能先買後賣，不可以先賣後買。
• 每次買與賣都限定是一個單位的商品。同時，在買入之後，賣出之前，不可以再買入。
• 由於法令的規定，在此期間內最多只能進行K 次的交易(一次交易包含買賣各一次)。
輸入的資料是AI-666 系統所預測N 個時間點的商品價格以及一個正整數K，請計算不
超過K 次交易的條件下最大可能獲得的利益。
舉例來說，以下資料是11 個時間點的價格：
| 時間點 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 價格 | 100 | 90 | 185 | 120 | 80 | 150 | 140 | 180 | 110 | 150 | 50 |
如果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。
每筆測資共有二行。第一行為兩個正整數N 與K，分別代表時間點數與交易次數上限，
其中N>1。第二行有N 個以空白間隔的正整數，依序是各時間點的價格。每一價格均為不超
過10,000,000 的正整數，每筆測資的最大可能獲利不超過1,500,000,000。
以單獨一行輸出不超過K 次交易的最大可能獲利，若無法獲利則應輸出0。
輸入範例 1： 11 1 100 90 185 120 80 150 140 180 110 150 50 輸入範例 2： 11 2 100 90 185 120 80 150 140 180 110 150 50 輸入範例 3： 11 5 100 90 185 120 80 150 140 180 110 150 50 輸入範例 4： 3 1 100 100 85
輸出範例 1： 100 輸出範例 2： 195 輸出範例 3： 245
本題共有四個子題，每一子題可有多筆測試資料，全部解出可獲該子題的分數。
第一子題（13 分）：N ≤ 1,000、K = 1。
第二子題（24 分）：N ≤ 50,000、K ≤ 100。
第三子題（45 分）：N ≤ 200,000、K ≤ N。
第四子題（18 分）：N ≤ 2,000,000、K ≤ N。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||