AGC 030 B - Tree Burning

• 問題

解法

お絵描きしたのでメモ.

部分点は O(N²) の区間DP.

それ以上に早くやるにはどうするか.
遷移が O(1) なので状態を減らすしかない.
しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない.
よってある状態(操作)を禁止して状態を減らすことを考える.

ここ とかがわかりやすい.

(直進) - (往復) - (直進) みたいな操作列が存在するならば,
最後の直進の終点が往復の終点になるように(直進) - (往復) の操作列に替えることができて,
これは元の移動距離よりも大きくなる.
よって (直進) - (往復) の操作列だけを考えてよく,状態が減らせた.

あとは累積和を使えばO(N)で解ける.