2020-05-03 2013JOI予選4 暑い日々 解説 JOI 解説 問題リンク 解説 基本的な動的計画法の問題です。 を、 日目までで、 日目に 番目の服を着た時の、派手さの絶対値の合計の最大値、とします。 遷移は、前の日の服と今日着る服がわかっていればできるので、今日着る服を決めることで合計 になります。 この問題は、JOI難易度5のDPとしては難しい部類だと思います。 このような、遷移が とは限らないDPも存在するということに注意しましょう。
![dp\left[i\right]\left[j\right]](https://chart.apis.google.com/chart?cht=tx&chl=dp%5Cleft%5Bi%5Cright%5D%5Cleft%5Bj%5Cright%5D)
を、
日目までで、 日目に 
番目の服を着た時の、派手さの絶対値の合計の最大値、とします。
遷移は、前の日の服と今日着る服がわかっていればできるので、今日着る服を決めることで合計 
になります。
とは限らないDPも存在するということに注意しましょう。