CF372C Watching Fireworks is Fun 发表于 2021-02-06 更新于 2023-08-02 分类于 oi ， 总结 ， dp CF372C Watching Fireworks is Fun 单调队列优化区间 dp 设 f(i,j)f(i,j)f(i,j) 表示放到第 iii 个烟花，当前在 jjj 的位置，设可以在两次烟花之间的移动距离为 sss 可以发现 f(i,j)=minj−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 f(i,j)=j−s≤k≤j+smin(f(i,k))+bi−∣ai−j∣ 用单调队列维护，加滚动数组，时间复杂度 O(nm)O(nm)O(nm) ，空间复杂度 O(n)O(n)O(n)