PythonでJOI難易度5を埋める #6
考えたこと
前から貪欲に取っていけば大丈夫だと思っていたけど、それだとダメだったのでDPします。
の
で初期化したdpテーブルを考えます。
[1:]]を
<h[i]]を満たすように更新していきます。もし条件を満たすなら
]を、満たさないなら
で更新します。
私は理解するのに時間がかかったので、入力例のdp遷移を見てみましょう。
input：3,7,5,9,8,10,10,11,9
更新される部分だけ見てみます。
dp[1] = [ 0. 3. inf inf inf inf inf inf inf inf]
dif = [ 7. 7. inf inf inf inf inf inf inf inf]
dp[2] = [ 0. 3. 7. inf inf inf inf inf inf inf]
dif = [ 5. 5. inf inf inf inf inf inf inf inf]
dp[3] = [ 0. 3. 5. inf inf inf inf inf inf inf]
dif = [ 9. 9. 9. inf inf inf inf inf inf inf]
dp[4] = [ 0. 3. 5. 9. inf inf inf inf inf inf]
dif = [ 8. 8. 8. inf inf inf inf inf inf inf]
dp[5] = [ 0. 3. 5. 8. inf inf inf inf inf inf]
dif = [10. 10. 10. 10. inf inf inf inf inf inf]
dp[6] = [ 0. 3. 5. 8. 10. inf inf inf inf inf]
dif = [10. 10. 10. 10. inf inf inf inf inf inf]
dp[7] = [ 0. 3. 5. 8. 10. inf inf inf inf inf]
dif = [11. 11. 11. 11. 11. inf inf inf inf inf]
dp[8] = [ 0. 3. 5. 8. 10. 11. inf inf inf inf]
dif = [ 9. 9. 9. 9. inf inf inf inf inf inf]
dp[1] → dp[2]は、なので、7が更新されます
dp[2] → dp[3]は、なので、5で更新されます
dp[3] → dp[4]は、なので、9で更新されます
dp[4] → dp[5]は、なので、8で更新されます
dp[5] → dp[6]は、なので、10で更新されます
dp[6] → dp[7]は、なので、更新されません
dp[7] → dp[8]は、なので、11で更新されます。
numpyを使うとdpの更新が楽なので使います。
import numpy as np n = int(input()) h = [int(input()) for _ in range(n)] inf = float('inf') dp = np.full((n,n+1), inf) dp[0][0] = 0 dp[0][1] = h[0] for i in range(1,n): dif = np.where(dp[i-1] < h[i], h[i], inf) #dp更新 dp[i][1:] = np.minimum(dif[:-1],dp[i-1][1:]) dp[i][0] = 0 ans = dp[-1][dp[-1]<inf] #infでない個数が答え print(len(ans)-1)
