問題の説明

質問する

国際資本不動産会社はByte Coinに投資している.ビットコインは金博士が作った仮想通貨だ.実際にバイトコードの価格を予測することはできないが,この問題ではバイトコードの価格上昇を事前に正確に予測できると仮定する.
1日からn日までのn日間、図1に示すように、バイトコードの上昇と下落を予め知ることができ、初期現金Wがあります.図1の赤いボックスは、その日付のバイトコード価格を示す.毎日ビットコインを買収したり売ったりすることができます.しかし、ビットコインを1つに分けて投げ売りや買収することはできません.私たちはn日に持っているすべての硬貨を販売する際に、持っている現金を最大化することを望んでいます.

例えば、図1に示すバイトコードの立ち上がり図を初日に知ることができ、私たちに与えられた初期現金は24であると仮定することができる.収益を最大限に高めるには、ビットコインを以下の方法で買収、販売することができます.初日に現金20元でコインを4個買いました.翌日、すべての硬貨を売って、28の現金を得て、全部で32の現金があります.5日目に32現金で16個の硬貨を買収した.7日目にすべてのコインを売って、全部で128ドルの現金を手に入れた.9日目には現金126で42個の硬貨を購入し、10日目にはすべての硬貨を販売した.では、10日の現金は170に達し、これが最大です.
曜日n、初期現金W、1日からn日まで毎週1バイト硬貨の価格、n日に持っているすべての硬貨を売る場合、持っている最終現金の最高値を書いてください.

入力

入力は標準入力です.第1行は、曜日を表す正の整数nおよび初期現金W(1≦n≦15、1≦W≦100000)を与える.次のn行では、iの1行目は、i日バイトコードの価格(1≦si≦50)を表す整数siを与える.

しゅつりょく

出力は標準出力を採用する.n日に所持している全ての硬貨を売る場合、現金の最高値を1行に印刷する.なお、初期現金Wはそれほど大きくないが、最終的には現金が大きくなる可能性がある.

提问链接

完全なコード

import sys

input = sys.stdin.readline 

n, w = map(int, input().split())

s = []
for _ in range(n):
    s.append(int(input()))

current = [s[0]]

for i in range(1, n):
    if current[-1] <= s[i]:
        current.append(s[i]) 
    else:
        if len(current) == 1:
            current = [s[i]]
        else:
            count = w // current[0]
            w = w % current[0]
            w += (count * current[-1])
            current = [s[i]]

if len(current) > 1:
    count = w // current[0]
    w = w % current[0]
    w += (count * current[-1])
    
print(w)

解決策

この問題で私たちが考えなければならないのは、株価が熊市に入ったとき、価格が一番高いときに一番低いところで買った株を売るべきだということです.これは最大のヒントです.