n133. p5. 大雄的煩惱
標籤 : DP
通過比率 : 6人/9人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-08-27 04:23

內容

  大雄某天回家之後,發現爸爸因為投資股票失利而心情不佳,為了幫助爸爸,大雄與哆啦A夢決定乘坐時光機,到未來幾天查看股價,再回到現在告訴爸爸,但隨著來回次數漸漸多了起來,哆啦A夢害怕引起時空警察的盤查,想到了一個絕妙的點子,那就是寫出一套自動化的股票交易系統。
  然而,如何撰寫進行股票交易的程式,以大雄 $0$ 分的腦袋是想不出來的,只好讓我們幫幫他囉~
  在得到來自未來的資料庫之後,我們就會知道未來 $n$ 天的股票價格,看準價格買入股票並在未來的日期高價賣出。不過要注意的是,交易者最多可以進行 $t$ 筆交易,其中新交易只能在前一筆交易完成後才能繼續,而系統會自動進行股票交易並獲得這期間的最大利潤(買賣須扣除手續費 $0.1\%$)。
  舉例來說,資料庫回傳了未來 $6$ 天的股價,[$10$, $22$, $5$, $75$, $65$, $80$](單位:千元),然後我們這次最多進行 $2$ 次買賣交易,系統會知道應該第一天買 $10$ 第二天賣 $22$,然後第三天再買 $5$ 等到第六天賣 $80$,扣除手續費 $0.1\%$ 後,利潤為
$$(22000-10000)+(80000-5000)-(22000+10000+80000+5000)×0.1\%$$,得到最大利潤 $86883$ 元。

輸入說明

1) 第一行為一正整數 $t$ ($1\leq t\leq 10$),代表交易者最多可以進行 $t$ 筆交易。
2) 第二行為一正整數 $n$ ($2\leq n\leq 100$),代表總共回傳 $n$ 天的股票價格。
3) 第三行輸入 $n$ 筆股票價格,股票價格 $p$ ($0\leq p\leq 1000$),以空白隔開。

輸出說明

  輸出一個整數,代表最大利潤。

範例輸入 #1
2
6
10 22 5 75 65 80
範例輸出 #1
86883
範例輸入 #2
1
5
100 80 80 70 50
範例輸出 #2
0
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
DP
出處:
110新北市資訊學科能力複賽 [管理者: liaoweichen1 ... (M_SQRT) ]

本題狀況 本題討論 排行

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