2020-06-20 2008JOI春合宿2-1 Nile.Com 解説 JOI 解説 問題リンク 解説 動的計画法の問題です。 たとえば、 を 日目に、前日店 で買い物をし、そこでは 日連続で買い物をしている、という場合の最小の合計金額とすると、 で解くことができます。 このように、最終的な最適解が、条件を絞れば途中まででも必ず最適解となる場合は、最適化問題にDPを採用できる場合が多いです。 今回のような少し複雑な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)
を 
日目に、前日店 
で買い物をし、そこでは 
日連続で買い物をしている、という場合の最小の合計金額とすると、
で解くことができます。