【单调队列DP】烽火传递

**

1565 – 【堆练习】烽火传递3577

**
Description
　　烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。在某两个城市之间有n(n<=200000)座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续m个烽火台中至少要有一个发出信号。现在输入n,m和每个烽火台的代价(代价小于等于1000)，请计算总共最少的代价在两城市之间来准确传递情报。
Input
　　第一行是n,m表示n个烽火台和连续烽火台数m
　　第二行n个整数表示每个烽火台的代价。
Output
　　输出仅一个整数。
Sample Input
5 3
1 2 5 6 2
Sample Output
4

设f[i]表示从开始到第i个数字并且第i个数字必须选，满足题
目条件的最小代价和。则：
n F[i]=min{f[j]}+a[i]，(i-m<=j<=i-1)
n 求f[i]时： 要求区间{f[i-m],f[i-m+1],…,f[i-1]}中的最小值；
n 求f[i+1]时：要求区间{f[i-m+1],…,f[i-1],f[i]}中的最小值；
n 初始化：f[i]=a[i]，(1<=i<=m)
n Ans=min{f[i]}，(n-m+1<=i<=n)

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=200005;
int n,m,f[maxn],a[maxn],q[maxn];
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int main()
{
	int i,j,head=0,tail=0;
	n=read();m=read();
	for(i=1;i<=n;i++)a[i]=read();
	for(i=1;i<=m;i++)
	{
		f[i]=a[i];
		while(tail>0&&a[i]<=a[q[tail]])tail--;
		q[++tail]=i;
	}
	for(i=m+1;i<=n;i++)
	{
		while(head<=tail&&q[head]<i-m)head++;
		f[i]=f[q[head]]+a[i];
		while(head<=tail&&f[q[tail]]>=f[i])tail--;
		q[++tail]=i;
	}
	int ans=0x7fffffff/2;
	for(i=n-m+1;i<=n;i++)ans=min(ans,f[i]);
	cout<<ans;
	return 0;
}