思路

定义f[i]表示以第i个烽火台为结尾的可以传递信号的最低花费

python 单调队列优化DP

from typing import List
class Solution:
    def main(self, n:int, m:int, a:List[int]):
        f=[0 for _ in range(n+1)]
        q=[0]
        for i in range(1, n+1):
            if q and q[0]<i-m: q.pop(0)
            f[i]=f[q[0]]+a[i-1]
            while q and f[q[-1]]>=f[i]: q.pop(-1)
            q.append(i)

        res=float('inf')
        for i in range(n-m+1, n+1): res=min(res, f[i])
        print(res)

if __name__ == '__main__':
    n, m=map(int, input().split())
    a=list(map(int, input().split()))
    sol=Solution()
    sol.main(n, m, a)

c++ 单调队列优化DP

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
int n,m;
int w[N], f[N];
deque<int> q;

int main(){
    // 单调队里优化DP
    memset(f, 0x00, sizeof f);
    cin>>n>>m;
    for(int i=1; i<=n; ++i) cin>>w[i];
    q.push_back(0);
    for(int i=1; i<=n; ++i){
        if(!q.empty() && q.front()<i-m) q.pop_front();
        f[i]=f[q.front()]+w[i];
        while(!q.empty() && f[q.back()]>=f[i]) q.pop_back();
        q.push_back(i);
    }

    int res=1e9;
    for(int i=n-m+1; i<=n; ++i) res=min(res, f[i]);
    cout<<res<<endl;

    return 0;
}