刷题总结——烽火传递（单调队列+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 范围内。

题解：

要用动态规划的方法解决。
我们可以写出这样的方程f[i]:=min{f[j]}+a[i]（i-m<=j<i-1）
因为要保证i之前的3个中必须存在被点亮的烽火台。单纯这样循环会造成超时。

我们想到了用单调队列进行优化，由于随着i的循环，每次只有一个i进入决策区间也只有一个i出决策区间，由于每次选取决策区间中的最小值，所以维护一个单调递增序列，每次取出队首元素即可。

为什么可以将队尾元素无情的删去呢？由于后进队的序列同时满足在原序列中的位置更靠后和其在动态规划中的价值更大。这样选取这个元素就要比选取之前的任何一个决策要优，所以之前被删掉的决策都是无用的。

这道题的本质就是用单调队列维护了决策本身的价值和其在原序列中位置的同时单调。
要特别注意单调队列中的值是决策在原决策序列中的位置。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int inf=1e+9;
const int N=1e6+5;
int n,m,w[N];
int que[N],head,tail,dp[N];
inline int R()
{  
  int f=0;
  char c;
  for(c=getchar();(c<'0'||c>'9');c=getchar());
  for(;c>='0'&&c<='9';c=getchar())
    f=(f<<3)+(f<<1)+c-'0';
  return f;
}
int main()
{
  //freopen("a.in","r",stdin);
  n=R(),m=R();
  for(int i=1;i<=n;i++)
    w[i]=R();
  head=1,tail=1;
  dp[1]=w[1];
  que[1]=1;
  int temp=inf;
  for(int i=1;i<=m;i++)
    dp[i]=min(temp,w[i]);
  for(int i=2;i<=n;i++)
  {
    if(i>m)   
      dp[i]=dp[que[head]]+w[i];
    tail++;   
    while(dp[i]<=dp[que[tail-1]]&&tail>head)  tail--;
    que[tail]=i;
    if(que[tail]-que[head]>=m)  head++;
  }
  int ans=inf;
  for(int i=n;i>=n-m+1&&i>=1;i--)
    ans=min(ans,dp[i]);
  cout<<ans<<endl;
  return 0;
}