题解：AT_arc168_d [ARC168D] Maximize Update

one_last_kiss · 2025-10-28 15:43:04 · 题解

[ARC168D] Maximize Update

数据范围 n \le 500，很明显可以看出是区间 dp。

令 dp_{l,r} 为把 l 到 r 的格子涂成黑色的改变状态的次数最大值。

转移时，我们枚举 l 到 r 之间的白色格子断点 k，即方程为 dp_{l,r} = dp_{l,k-1}+dp_{k,r}+w_{l,r,k}。