c457. 6. AI-666 賺多少 - 高中生程式解題系統

內容

商品價格經常是起起伏伏，例如石油的價格幾乎時時都有變動，有時上漲，有時下跌。
商品交易商在低價時買進高價賣出就可以利用其中的價差獲取利益。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

輸入範例 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

輸出範例 1：
100

輸出範例 2：
195

輸出範例 3：
245

測資資訊：

記憶體限制： 512 MB

提示：

本題共有四個子題，每一子題可有多筆測試資料，全部解出可獲該子題的分數。
第一子題（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。

標籤:

出處:

106學年度全國資訊學科能力競賽 [管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」