BOJ17521 Byte Coin FiSun

質問する

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

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

入力

入力は標準入力です.最初の行の曜日を表す正の整数. nと初期現金 W(1 ≤ n ≤ 15, 1 ≤ W ≤100000).次です. n 犬の行の中で、 最初の行は i日バイトコードの価格を表す整数. Siを与える(1≦ si ≤ 50).

しゅつりょく

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

N,W = map(int,input().split())
S = [int(input()) for _ in range(N)]
maxv= max(S)
buy_price = maxv
coin = 0

for i in range(N-1):
    #다음꺼가 더 클 때 지금 가격에 구매
    if S[i+1]>S[i]:
        buy_price = min(buy_price,S[i])
        coin = W // buy_price
        minus =  buy_price * coin
    #다음께 작으면 판매
    elif S[i+1]<S[i] and coin != 0:
    #판매
    #돈 차감
        W += S[i]*coin-minus
        buy_price = maxv
        coin=0

if coin!=0:
    W += S[-1]*coin-minus

print(W)

次の日はもっと高くて、安くて売っています.
しかし「明日が今日より安ければ、今日の価格で買う」という論理を立てておけば、最低価格の日でなくても買うことになるので、minで比較すると、もっと安い価格が加算されます.
方法は頭の中にありますが、コードで表現する能力はまだ未熟なので、時間がかかりました.
また,変数名は思考が山積みになり,直接符号化に入ると,中には考えられない.
より詳細な計画を立てて符号化を開始する必要があるようです.