c457: 6. AI-666 賺多少
標籤 :
通過比率 : 0% (0 人 / 0 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-12-28 07:09

內容

商品價格經常是起起伏伏,例如石油的價格幾乎時時都有變動,有時上漲,有時下跌。
商品交易商在低價時買進高價賣出就可以利用其中的價差獲取利益。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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (3%): 0.7s , <1K
公開 測資點#1 (2%): 0.7s , <1M
公開 測資點#2 (2%): 0.7s , <1M
公開 測資點#3 (2%): 0.7s , <1M
公開 測資點#4 (2%): 0.7s , <1M
公開 測資點#5 (2%): 0.7s , <1K
公開 測資點#6 (3%): 0.7s , <1M
公開 測資點#7 (3%): 0.7s , <1M
公開 測資點#8 (3%): 0.7s , <1M
公開 測資點#9 (3%): 0.7s , <1M
公開 測資點#10 (3%): 0.7s , <1M
公開 測資點#11 (3%): 0.7s , <1M
公開 測資點#12 (3%): 0.7s , <1M
公開 測資點#13 (3%): 0.7s , <1K
公開 測資點#14 (6%): 0.7s , <1M
公開 測資點#15 (6%): 0.7s , <1M
公開 測資點#16 (6%): 0.7s , <10M
公開 測資點#17 (6%): 0.7s , <10M
公開 測資點#18 (6%): 0.7s , <10M
公開 測資點#19 (5%): 0.7s , <10M
公開 測資點#20 (5%): 0.7s , <10M
公開 測資點#21 (5%): 0.7s , <1K
公開 測資點#22 (2%): 0.7s , <10M
公開 測資點#23 (2%): 0.7s , <10M
公開 測資點#24 (2%): 0.7s , <50M
公開 測資點#25 (2%): 0.7s , <50M
公開 測資點#26 (2%): 0.7s , <50M
公開 測資點#27 (2%): 0.7s , <50M
公開 測資點#28 (2%): 0.7s , <50M
公開 測資點#29 (2%): 0.7s , <50M
公開 測資點#30 (2%): 0.7s , <1K
提示 :

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


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