技術室奥プログラミングコンテスト#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