【烽火传递】dp + 单调队列优化

2023-01-27 11:36:01

题目描述

烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在 m 个烽火台中至少要有一个发出信号。现输入 n、m 和每个烽火台发出的信号的代价，请计算总共最少需要多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递！

输入格式

第一行有两个数 n，m 分别表示 n 个烽火台，在任意连续的 m 个烽火台中至少要有一个发出信号。
第二行为 n 个数，表示每一个烽火台的代价。

输出格式

一个整数，即最小代价。

样例数据 1

输入

5 3
1 2 5 6 2

输出

4

备注

【数据范围】

1<=n，m<=1,000,000，保证答案在 int 范围内。
1<=n，m<=1,000,000，保证答案在 int 范围内。

题目分析

首先考虑dp，因为每m个点中必须选择2个，那么对于当前点（i），$f[i] = min\{f[j]\}+ val[i] (i - m + 1 ≤ j < i )$

这样的每次要去寻找最小值，复杂度报表，考虑dp优化。

由于要取最小值，那么就可以维护一个单调递增的单调队列，每次入队维护单调性，并删除队首不在区间中的数，然后队首就是要找的最小值。

这样下来，时间复杂度$o(n)$

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

using namespace std;

const int N = 1e6 + , oo = 0x3f3f3f3f;

struct node{

    int val, id;

};

node que[N];

int cost[N], head, tail, i, f[N];

int n, m;

inline int read(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline void wr(int x){

    if(x < ) putchar('-'), x = -x;

    if(x > ) wr(x / );

    putchar(x%+'');

}

int main(){

    n = read(), m = read();

    for(i = ; i <= n; i++) cost[i] = read();

    head = , tail = ;

    for(i = ; i <= n; i++){

        while(que[head].id < i - m && head <= tail) head++;

        f[i] = que[head].val + cost[i];

        while(tail >= head && que[tail].val >= f[i]) tail--;

        que[++tail] = (node){f[i], i};

//        for(int j = head; j <= tail; j++) cout<<que[j].val<<" ";cout<<endl;

    }

    int ans = oo;

    for(int i = n - m + ; i <= n; i++)

        ans = min(ans, f[i]);

    cout<<ans<<endl;

    return ;

}

码农公寓