烽火传递

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 981 字

n个烽火台，连续m个中至少1个发信号，求最小

一本通
练习

正文

/*
原题：T1602 「一本通 5.5 练习 1」烽火传递
题意：n 个烽火台，连续 m 个中至少 1 个发信号，求最小总代价。
思路：dp[i]=在第 i 个发信号时前 i 个的最小代价 = a[i]+min(dp[j])，j 在 [i-m,i-1]；
     用单调队列维护窗口内最小 dp[j]（含虚拟 dp[0]=0）。答案为最后 m 个 dp 的最小值。
复杂度：时间 O(n)，空间 O(n)。
易错点：dp[0]=0 充当“起点窗口已被覆盖”；答案为最后 m 个位置的最小值（末窗须含信号）。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<long long> dp(n+1,LLONG_MAX);
    dp[0]=0;
    deque<int> q;
    q.push_back(0);
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front()<i-m){
            q.pop_front();
        }
        dp[i]=a[i]+dp[q.front()];
        while(!q.empty()&&dp[q.back()]>=dp[i]){
            q.pop_back();
        }
        q.push_back(i);
    }
    long long ans=LLONG_MAX;
    int lo=max(1,n-m+1);
    for(int i=lo;i<=n;i++){
        ans=min(ans,dp[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

烽火传递

正文

一本通·提高篇的其它内容