7K12 blog

猫でも分かるアルゴリズム解説

パ研合宿2019 D - パ研軍旗

f:id:tkr987:20200513142018p:plain

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/13169571

  • DP初期値は0
  • DP繰り返しはrep(i, 0, N) rep(0, j, 5)
  • DP更新はDP[i][R] = min(DP[i-1][B], DP[i-1][W]) + count[i][R]など
  • DP出力はmin({DP[N-1][R], DP[N-1][B], DP[N-1][W]})
  • 入力の先頭にダミーを追加するとDPの初期値を0にすることができるので、実装が楽になる

f:id:tkr987:20200513215110p:plain

DP[i][c]をi列目に色cにしたとき塗り替えたマス合計とする。予めi列目を赤、青、白、にしたときi列目を何枚塗るか前処理でカウントしておき、その情報をもとにDPで処理していく。予め入力の先頭にダミーを追加してN++しておくと実装が楽になる。