[伯俊-1106]ジャンプ

5750 ワード
パイ 白駿 DP テキストリンク

マイコード

import sys
input = sys.stdin.readline

n=int(input())
maze=list(map(int,input().split()))

dp=[1001]*n
dp[n-1]=0
for i in range(n-2,-1,-1):
    if maze[i]==0:
        dp[i]=-1
        continue
    for j in range(1,maze[i]+1):
        if i+j>=n:
            break
        if dp[i+j]<dp[i] and dp[i+j]!=-1:
            dp[i]=dp[i+j]
    if dp[i]==1001:
        dp[i]=-1
    else:
        dp[i]+=1

print(dp[0])

実行時間:72ミリ秒


に答える


私は最後から初めて帰ってきて、最小ジャンプ回数を求める方法で問題を解いた.
たとえば、入力
n=10
maze=[1 2 0 1 3 2 1 5 4 2]
これであげると.
dp[9]は9号室から9号室までの最小ジャンプ回数であるため0である.
dp[8]は8号室から9号室までの最小ジャンプ回数である.ダンジョン[8]は4で、9、10、11、12号室にジャンプでき、ジャンプできる部屋から9号室にジャンプでき、最小ジャンプ回数+1の値はdp[8].この時は10、11、12号室がないので無視.したがって、dp[8]=1となる.
7号室から9号室までの最小ジャンプ回数は、迷宮[7]=5で、8、9号室までジャンプできる.したがって、dp[8]およびdp[9]では、最小値に+1を加えた値がdp[7]であり、その値は1である.
迷路[i]が0の場合はジャンプできないため、dp[i]=-1としてスキップします.
また、i号室に最後の部屋に飛び込めない部屋がある場合は、まずすべてのジャンプ可能な部屋を調べることを無視し、最後の部屋に飛び込めない場合はdp[i]=-1とする.
(一):文字列関連
[MYSQL]Webアプリケーションの作成-記事の詳細