ツバサの備忘録

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

ABC063 C - Bugged

問題
提出コード

解法

CはDPのC!(n回目)解説PDFによるとオーバーキル解法だそうです…
dp[i][j] = s_iまでを利用して、合計得点を10で割った余りがjとなるような得点の取り方の最大値
としてDPを解いていきます。
これは、
dp[i][(k+s_i)\%10] = max(dp[i-1][(k+s_i)\%10],dp[i-1][k]+s_i )
で解くことができます。
最終的な答えは、
dp[n][k]
の、k \neq 0の部分のうちの最大値です。