【yukicoder】No.37 遊園地のアトラクション

問題

週末yukicoder。ずっと動的計画法の練習です。

解法

おなじみ動的計画法で解きます。一度選んだアトラクションが再度選べるのとその際価値が前回の半分（切り捨て）になるところが、ちょっといつもの問題と違うところですね。
アトラクションの価値が元は]ですが、この配列に重複を含めた値も追加します。価値の最大は500なので、ずっと同じアトラクションに乗ることはなく、多くても９回です。

サンプル１でみると重複を含めたアトラクションの待ち時間と価値の配列は、

$$ \binom{c}{v}=\begin{pmatrix} 1 & 2 & 3 & 1 & 2\\ 3 & 2 & 1 & 1 & 1 \\ \end{pmatrix} $$

後ろ２列はアトラクション１の２回目、アトラクション２の２回目の待ち時間と価値です。 あとはこの重複を含めたアトラクションの配列を先頭から見ていって、の行列を作って解くだけです。

簡単な動的計画法の問題は【yukicoder】No.1 道のショートカットで解きましたのでそちらを参考ください。

Python3

コード

import math
T=int(input())
N=int(input())
C=list(map(int,input().split()))
V=list(map(int,input().split()))
Z=list(zip(C,V))
Z2=Z[:]
for z in Z:
    c=z[0]
    v=z[1]
    while True:
        v=math.floor(v/2)
        if v<=0:
            break
        Z2.append((c,v))
A=[[0]*(T+1) for i in range(len(Z2)+1)]
for i in range(1,len(Z2)+1):
    for t in range(1,T+1):
        z=Z2[i-1]
        c=z[0]
        v=z[1]
        if t-c<0:
            A[i][t]=A[i-1][t]
        else:
            A[i][t]=max(A[i-1][t-c]+v,A[i-1][t])
print(max(list(map(max,A))))