1089 烽火传递（单调队列优化）

小鱼儿 2022-08-28 09:00 179阅读 0赞

**1. 问题描述：**

烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。在某两个城市之间有 n 座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 m 个烽火台中至少要有一个发出信号。现在输入 n，m 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

**输入格式**

第一行是两个整数 n，m，具体含义见题目描述；第二行 n 个整数表示每个烽火台的代价 ai。

**输出格式**

输出仅一个整数，表示最小代价。

**数据范围**

1 ≤ n，m ≤ 2 × 10 ^ 5，

0 ≤ ai ≤ 1000

**输入样例：**

5 3  
1 2 5 6 2

输出样例：

4  
来源：[https://www.acwing.com/problem/content/description/1091/][https_www.acwing.com_problem_content_description_1091]

**2. 思路分析：**

分析题目可以知道这是一个最优化问题，所以我们考虑使用**动态规划**的思想来解决。根据题目的描述我们可以知道我们声明一个一维数组f，其中f\[i\]表示点燃第i个烽火台的最小花费；怎么样进行状态计算呢？状态计算一般是找最后一个不同点，我们可以枚举倒数第二个位置的最小花费，可以发现倒数第二个位置的烽火台的位置可以是i - m，i - m + 1....i - 1，所以枚举这些位置的最小花费累加到当前位置即可，而这是一个区间的最小值问题，所以可以使用**单调队列**进行优化，在队列中维护长度不超过m的最小花费对应的位置即可，经过优化之后那么就不用使用额外的循环来枚举整个连续的区间求解最小值了。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == '__main__':
        n, m = map(int, input().split())
        w = [0] + list(map(int, input().split()))
        q = [0] * (n + 1)
        # hh为队头指针, tt为队尾指针, tt = -1时表示为空, 0时表示有一个元素
        hh, tt = 0, 0
        # f[0]其实也是一种方案，一开始的队头元素是0
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            # 一般边界问题可以通过画图确定
            if q[hh] < i - m: hh += 1
            f[i] = f[q[hh]] + w[i]
            while hh <= tt and f[q[tt]] >= f[i]: tt -= 1
            tt += 1
            q[tt] = i
        res = 10 ** 9
        # m个连续的烽火台其实是m + 1个烽火台所以在枚举的时候为n - m + 1
        for i in range(n - m + 1, n + 1):
            res = min(res, f[i])
        print(res)

[https_www.acwing.com_problem_content_description_1091]: https://www.acwing.com/problem/content/description/1091/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/69ad3a3d4a8f4451a22d0b4b0e793a14.png