JOI2008春合宿 A nile - ナイルドットコム (Nile.Com)

問題概要
思考の流れ
提出プログラム
感想

問題概要

${2\le N\le 3000}$ 店舗から ${2\le D\le 365}$ 日間 ${1}$ 店舗選んで商品を( ${1}$ 日 ${1}$ 店舗のみから必ず)買う). 商品の値段は ${10}$ の倍数で与えられ, 毎日各店舗で値段が変わる. ${2}$ 日連続で同じ店で買うと ${1}$ 割引, ${3}$ 日連続同じ店で買うと ${3}$ 割引になる. このとき, ${D}$ 日間で買う商品の値段の最小値を求めよ.

思考の流れ

以下, ${i+1}$ 日目の ${j}$ 番目の店の値段を ${c_{ij}}$ とする.
どの店で何日連続で買ってるか, という情報をもつDPを行えばよさそう. ${dp[i][j][k]}$ を「 ${i+1}$ 日目に ${j}$ 番目の店で ${k+1}$ 日連続で買ってる時の最小(3日以上買うときは ${k=2}$ )」とすると更新式は

${dp[i][j][0]=}$ ( ${j'\neq j}$ かつ ${1\le j'\le N}$ で ${k'=0,1,2}$ をみたす ${dp[i-1][j'][k']}$ の最小値) ${+c_{ij}}$ ${dp[i][j][1]=dp[i-1][j][0]+c_{ij}×0.9}$ ${dp[i][j][2]=\min(dp[i-1][j][1],dp[i-1][j][2])+c_{ij}×0.7}$