お釣りの嫌いな高橋君
- 問題
- 解法
dpをする.
i 番目のコインが有り余ってたら i + 1 番目のコインとして見なすことで、i 番目のコインを 0 ~ max(a[ i ] + 下からの傘増し, 9) しかないと思っても良い.
各ステップ i で下から傘増しされるコインの種類数はそんなに多くはないことから、mapを使って以下のようにdpテーブルを定義する.
dp[ i ][ j ][ k ] : 右から i 桁目まで処理した後、i 桁目の値が j で、i + 1 番目のコインが k 枚増えるような決め方の場合の数.
最後に全部ゼロ枚使う場合を引けばおしまい.
- 提出コード
