[Acwing] 1089. 烽火传递 单调队列优化dp

前言

传送门 :

思路

状态表示 f [ i ] f[i] f[i]以 i i i结尾的区间 状态计算 f [ i ] = f [ j ] m i n + w [ i ] f[i]=f[j]_{min}+w[i] f[i]=f[j]min​+w[i]

因此我们可以使用一个 滑动窗口维护一个 i − m < = j < = i − 1 i-m