这是一个单调队列优化动规问题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目要求:在 nnn个烽火台中,每连续 mmm个烽火台中至少有一个发出信号,求最小总代价。
这可以转化为:选择若干个位置点燃烽火,使得任意两个相邻被选中的位置之间的距离不超过 mmm
(或者更准确地说,对于任意区间 [i−m+1,i][i−m+1,i][i−m+1,i],其中至少有一个被选中)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
动规状态定义:
设 f[i]f[i]f[i] 表示:前 iii 个烽火台满足条件,且第 iii个烽火台一定发出信号时的最小代价。
状态转移方程:
如果第iii个烽火台发出信号,那么上一个发出信号的烽火台jjj必须满足:i−j≤mi−j≤mi−j≤m(即 j≥i−mj≥i−mj≥i−m),这样才能保证jjj和iii之间的烽火台都被覆盖,且不会出现在某段长度为mmm的区间内没有信号的情况。
注意:这里隐含了一个边界处理,通常我们会引入一个虚拟的第000号烽火台,代价为000,作为起始点。
因此,转移方程为:
f[i]=a[i]+mini−m≤j<if[j]f[i]=a[i]+min _{i−m≤j<i}f[j]f[i]=a[i]+mini−m≤j<i f[j](fff数组中下标为i−mi-mi−m到iii中的最小值,jjj指的是找最小值时的下标)
其中a[i]a[i]a[i]是第iii个烽火台的代价。
最终答案:
ans=minn−m+1≤i≤nf[i]ans=min_{n−m+1≤i≤n }{f[i]}ans=minn−m+1≤i≤n f[i]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
优化:
直接做肯定会超时,我们观察转移方程,要求的是区间最小值,这明显是一个滑动窗口问题
所以我们用一个单调递增队列来维护,复杂度就是O(n)O(n)O(n)