[cdq优化dp] P4093

_Cheems · 2024-01-27 21:26:05 · 个人记录

思路

首先打出 O(n^2) 暴力 \rm dp。

然后算上时间维的话，转移条件就构成了三维偏序，可以放进 \rm cdq 里优化。

具体的，solve(l,r) 处理 l 到 r 的所有转移，递归进行 solve(l,mid)，然后计算 (l,mid) 向 (mid + 1,r) 的转移，最后进行 solve(mid+1,r)，注意这个顺序。