2013JOI予選4 暑い日々 解説

問題リンク

解説

基本的な動的計画法の問題です。

を、 日目までで、 日目に 番目の服を着た時の、派手さの絶対値の合計の最大値、とします。 遷移は、前の日の服と今日着る服がわかっていればできるので、今日着る服を決めることで合計 になります。

この問題は、JOI難易度5のDPとしては難しい部類だと思います。 このような、遷移が とは限らないDPも存在するということに注意しましょう。