Codeforces Round #464 (Div. 2) - F. Cutlet
難しかったので自分用メモ
バチャFはDP[i][j][k]:=i番目の区間までにj時間焼く、k==(カツレツが表) と定義すると、k個の区間それぞれについて
— heno (@heno_code) April 21, 2020
0回返す:区間長分足すだけ
1回返す:各lに対してdp[i+1][l][k^1]=min_{0<=j<=(区間長)}(dp[i][j][k]+1)
2回返す:1回と同様
になり、区間から貰うのはスライド最小値で可能、全部でO(NK)
これベースに理解した。
カツレツの両面を0と1とすると
dp[i][j][k] := i番目の区間まで見た時、今面kを焼いていて、0をj時間焼いたときのひっくり返す最小値
あとは区間の長さの分だけ自由な時間0の面を焼くことができるので、それに合わして上のツイートのように遷移していけばいい
ついでにslide最小値は関数にした。
提出コード
まとめ
これ理解するのにほぼ半日使っちゃった…
こういうのすらっとできるようになりたいね
