Dungeon Attack (Easy)

2 secs 1024 MB
magurofly's icon magurofly

解説

まずサンプル 1 を図示してみます。

サンプル1

正解となる通り方をするとこうなります。

サンプル2

このように、辺を何度も通ることでスコアを稼ぐことができます。

T,NT, NT,N100T, N \le 100 と小さいので、時刻が 0,1,2,,T0, 1, 2, \ldots, T のとき、それぞれの頂点における最大スコアを求めることを考えてみましょう。

dp[i][j]\text{dp}[i][j] を、時間 ii のときに地点 ii にいる場合の最大のスコアと定義します。

更新は以下のように行います。

dp[i][Bk]=max{dp[i][Bk],dp[i1][Ak]+Sk}\text{dp}[i][B_k] = \max\{ \text{dp}[i][B_k], \text{dp}[i - 1][A_k] + S_k \}

dp[i][j]=max{dp[i][j],dp[i1][j]}\text{dp}[i][j] = \max\{ \text{dp}[i][j], \text{dp}[i - 1][j] \}

このようにすることで、 O((N+M)T)O((N + M)T) で解くことができました。