ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC149 D - Prediction and Restriction

問題
提出コード

解法

次に出す手は、K手前の手にのみ依存します。
よって、じゃんけんの出す手は、Kで割った余りごとに独立して考えることができます。
dp[i][j] = i番目に出す手がjであるときにおける、i \ mod \  Kの手番についての得点の総和の最大値
とすると、答えは\displaystyle \sum_{i=N-K + 1}^{N} max(dp[i][j])
となります。
dp[i][j] = max(dp[i-k][k] + (jで勝てる場合はその得点) ) (j \neq k)
となります。

感想

貪欲でも解けるらしいのですが、証明を短時間で行うのが難しそうな上、DPの方が確実な気がします。
言われてみれば確かに…ってなりました。