烽火传递【单调队列】
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
烽火台是重要的军事防御设施,一般建在交通要道或险要处。
一旦有军情发生,则白天用浓烟,晚上有火光传递军情。
在某两个城市之间有 n 座烽火台,每个烽火台发出信号都有一定的代价。
为了使情报准确传递,在连续 m 个烽火台中至少要有一个发出信号。
现在输入 n, m 和每个烽火台的代价,请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
输入格式
第一行是两个整数 n,m,具体含义见题目描述;
第二行 n 个整数表示每个烽火台的代价 ai。
输出格式
输出仅一个整数,表示最小代价。
数据范围
1 ≤ m ≤ n ≤ 2 × 10 ^ 5
0 ≤ ai ≤ 1000
输入样例:
5 3
1 2 5 6 2
输出样例:
4
思考
我的滑动窗口题解 这道题就是单调队列的思想
我的修剪草坪题解 这两道题结合可以理解清楚下标和队列的问题
这道题我们使用一维的 f[i]
代表着从 1 -> i
的烽火台里面选取并点燃,且必定点燃 i
的情况的合法点燃序列(连续 m 个烽火台中至少要有一个发出信号)。而存储值为 Min(最小花费)
那么我们状态转移一定是考虑 i
之前的: f[i] = min{f[j]} + w[i]
, (i - m <= j < i
) 【不是 i - m + 1
是因为 i
还没入队】
故维护一个单调上升的单调队列即可。
java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, m, N = 200010;
static int[] w = new int[N];
static int[] f = new int[N];
static int[] q = new int[N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(s2[i-1]);
//模拟f[0]入队 故tt = 0
int hh = 0, tt = 0;
//f[0] = 0; 已经满足即可以省略初始化
for (int i = 1; i <= n; i++) {
if (q[hh] < i - m) hh++;
f[i] = f[q[hh]] + w[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt--;
q[++tt] = i;
}
int res = (int) 1e8;
for (int i = n - m + 1; i <= n; i++) res = Math.min(res, f[i]);
System.out.println(res);
}
}