人権なし

競プロで解いた問題や開発の進捗などの記録です

技術室奥プログラミングコンテスト#4 Day1:L - じゃんけん

問題

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l

解法

以下の DP を考える.

dp(i, j) := 頂点 i にいて,今 j 回まで操作が終わった時の,これから得られるスコアの総和の最大値

遷移は今いる頂点 i に留まるか,頂点 i につながる頂点のどれかに行くかを全て試し,これらのそれぞれのスコアの総和の最大値を dp(i, j) の答えとすればよい.じゃんけんの結果のスコアを返す関数を作っておくと DP 内のコードがスッキリして見やすい.O((N + M) * K).

解答

https://atcoder.jp/contests/tkppc4-1/submissions/6662685

f:id:babcs2035:20190803223927p:plain