CF372C Watching Fireworks is Fun

单调队列优化区间 dp

设 f(i,j)f(i,j) 表示放到第 ii 个烟花，当前在 jj 的位置，设可以在两次烟花之间的移动距离为 ss 可以发现

f(i,j)=min⁡j−s≤k≤j+s(f(i,k))+bi−∣ai−j∣f(i,j)=\min\limits_{j-s\le k\le j +s}(f(i,k))+b_i-\vert a_i-j\vert

用单调队列维护，加滚动数组，时间复杂度 O(nm)O(nm) ，空间复杂度 O(n)O(n)