admin 管理员组

文章数量: 1086057

[NOIP2010初赛]烽火传递

问题描述：
烽火台又称烽燧，是重要的军事防御设施，一般建在险要或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情，在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定代价。为了使情报准确地传递，在连续m个烽火台中至少要有一个发出信号。请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。
输入：
第一行：两个整数N，M。其中N表示烽火台的个数，M表示在连续m个烽火台中至少要有一个发出信号。接下来N行，每行一个数Wi，表示第i个烽火台发出信号所需代价。
输出：
一行，表示答案。
样例输入：
5 3
1
2
5
6
2
样例输出
4

数据范围：
对于50%的数据，M≤N≤1,000 。　　
对于100%的数据，M≤N≤ 100,000，Wi≤100。

算法分析
状态：f[i]表示在i这个烽火台发出信号的最少花费
转移方程：f[i] = min(f[j] + a[i]) (i-m <= j <= i-1)
对于50%的数据：时间复杂度O(nm)
对于100%的数据:我们需要进一步优化，我们发现小括号里面的(i-m<=j<=i-1)这是一个固定的长度，正好符号我们的单调队列，求某以固定区间的最值。由于随着i的循环，每次只有一个i进入决策区间也只有一个i出决策区间，由于每次选取决策区间中的最小值，所以维护一个单调递增序列，每次取出队首元素即可。目标状态为 f[n-m+1]…f[m] 中的最小值。
动态规划代码：

//烽火传递用动规
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int f[100500],a[100500];
int n,m;
int main() {int ans=0x7f7f7f7f;memset(f, 127, sizeof(f));scanf("%d%d", &n, &m);f[0] = 0;for(int i = 1; i <= n; i++) scanf("%d",&a[i]);for(int i = 1; i <= n; i++) for(int j=i-m;j<=i;j++)//枚举前m-1个烽火台，从哪个烽火台传递过来 {f[i]=min(f[j]+a[i] ,f[i]);//这个相当于找出前m-1个最小值，可以用队列优化 }for(int i = n - m + 1; i <= n; i++) ans = min(ans, f[i]);//从n-m+1烽火台再不需要点燃烽火台，终点都可以看到 printf("%d", ans);return 0;
}
/*
5 3
1
2
5
6
2
*/

用单调队列优化：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string> 
using namespace std;
const int maxn=100007;
int a[maxn],q[maxn],s[maxn];//s保存每个区间的最小值，q是模拟队列数组 
int ans=100;
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int head=0,tail=0;memset(s,-1,sizeof(s));//处置赋值为-1 q[0]=0;s[0]=0;for(int i=1;i<=n;i++){if(q[head]<i-m)//队首存储下标小于当前数下标的前m个数的下标//注意q保存的是下标而不是数值 {head++;//队列长度超出m，队头出队 }s[i]=s[q[head]]+a[i];//队头加 while(head<=tail&&s[q[tail]]>s[i]){tail--;//不满足单增队列 }q[++tail]=i;//i入队 }for(int i=n-m+1;i<=n;i++){ans=min(ans,s[i]);}printf("%d",ans);return 0;
}

本文标签： NOIP2010初赛烽火传递

版权声明：本文标题：[NOIP2010初赛]烽火传递 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693764586a241484.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。