首页 > 代码库 > 【烽火传递】dp + 单调队列优化
【烽火传递】dp + 单调队列优化
题目描述
烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有 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 + 5, 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 = 0, f = 1; char ch = getchar(); for(; (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘; ch = getchar()); if(ch == ‘-‘) f = -1, ch = getchar(); for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) i = (i << 3) + (i << 1) + (ch - ‘0‘); return i * f;}inline void wr(int x){ if(x < 0) putchar(‘-‘), x = -x; if(x > 9) wr(x / 10); putchar(x%10+‘0‘);}int main(){ n = read(), m = read(); for(i = 1; i <= n; i++) cost[i] = read(); head = 1, tail = 1; for(i = 1; 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 + 1; i <= n; i++) ans = min(ans, f[i]); cout<<ans<<endl; return 0;}
【烽火传递】dp + 单调队列优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。