题解：AT_arc168_d [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}$。

$w_{l,r,k}$ 即为包含 $k$ 且操作在 $l$ 到 $r$ 之间是否可行，类似于区间 dp，用 $w_{l+1,r,k}$ 和 $w_{l,r-1,k}$ 逐步往外扩展 $w_{l,r,k}$ 即可求出。