2020-05-03 2012JOI予選D パスタ 解説 JOI 解説 問題リンク 解説 基本的な動的計画法の問題です。 を、 日目までで、2日前に食べたパスタの種類が , 最後に食べたパスタの種類が のときの、 日目までのパスタの選び方の総数として遷移します。 遷移は自分で考えてみましょう。 本選を目指すなら15分以内には解けてほしい問題です。 DPの問題になるべくたくさん触れて練習しましょう。
![dp\left[i\right]\left[j\right]\left[k\right]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Cleft%5Bi%5Cright%5D%5Cleft%5Bj%5Cright%5D%5Cleft%5Bk%5Cright%5D)
を、
日目までで、2日前に食べたパスタの種類が 
, 最後に食べたパスタの種類が 
のときの、 日目までのパスタの選び方の総数として遷移します。
遷移は自分で考えてみましょう。