n133. p5. 大雄的煩惱 - 高中生程式解題系統

內容

　　大雄某天回家之後，發現爸爸因為投資股票失利而心情不佳，為了幫助爸爸，大雄與哆啦Ａ夢決定乘坐時光機，到未來幾天查看股價，再回到現在告訴爸爸，但隨著來回次數漸漸多了起來，哆啦Ａ夢害怕引起時空警察的盤查，想到了一個絕妙的點子，那就是寫出一套自動化的股票交易系統。
　　然而，如何撰寫進行股票交易的程式，以大雄 $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

範例輸入 #2

1
5
100 80 80 70 50

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (5%): 2.0s , <1K
公開測資點#3 (5%): 2.0s , <1K
公開測資點#4 (5%): 2.0s , <1K
公開測資點#5 (5%): 2.0s , <1K
公開測資點#6 (5%): 2.0s , <1K
公開測資點#7 (5%): 2.0s , <1K
公開測資點#8 (5%): 2.0s , <1K
公開測資點#9 (5%): 2.0s , <1K
公開測資點#10 (5%): 2.0s , <1K
公開測資點#11 (5%): 2.0s , <1K
公開測資點#12 (5%): 2.0s , <1K
公開測資點#13 (5%): 2.0s , <1K
公開測資點#14 (5%): 2.0s , <1K
公開測資點#15 (5%): 2.0s , <1K
公開測資點#16 (5%): 2.0s , <1K
公開測資點#17 (5%): 2.0s , <1K
公開測資點#18 (5%): 2.0s , <1K
公開測資點#19 (5%): 2.0s , <1K

提示：

標籤:

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

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