找了好半天也没找到可以注册&&提交本题得OJ，
所以不能保证AC。
描述
烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递！！！
输入格式 Input Format
第一行有两个数n,m分别表示n个烽火台，在m个烽火台中至少要有一个发出信号。
第二行为n个数，表示每一个烽火台的代价。
输出格式 Output Format
一个数，即最小代价。
样例
5 3
1 2 5 6 2
4
时间限制 Time Limitation
各个测试点1s
注释 Hint
1<=n,m<=1,000,000
题解：
一维线性dp，看上去是一眼秒得题。
dp[i]表示传到第i个峰台并且点亮了它时用的总最小代价。
dp[i] = min(dp[i-m]。。。。。dp[i-1]) + a[i]
（如果i-m到i-1中一个都没有点亮，那显然这m个就不符合题中：【每m个至少亮一个】的要求了）
最后dp[n-m+1]。。。。dp[n]中最小的一个即为所求。
但是我们注意到n、m都是1e6的范围。
那么这个的O(n*m)的算法就GG了。
但注意到整个过程，很像滑动窗口那道题，即每m个窗口中我们要选择最小的那个值和a[i]相加来更新dp[i].
我们只需要维护一个单增的队列，队列元素为峰台下标，当前点第i盏灯时，i-m以前的都没用了，不能用他们更新，所以pop_front。
然后队首即为这m个中的最小代价，用它更新dp[i]，上一个思路的O(m)部分就省下来了。
然后在把i加入队列之前，把比它大的值都pop_back掉，因为永远用不到它们来更新了，毕竟有离得更近，代价更低的第i盏。
复杂度：每个元素最多进出一次队列，所以并没有什么要担心的。O(n)。
用单调队列优化的dp方法有一定的规律性，简单来说就是可以看出滑动窗口的影子。
即有单调性。一定范围内只会用一个数组中的最大值或者最小值。
比较有名的应用应该是在优化多重背包的时候。
后面会更新到用单纯形法优化dp，算是更加神奇的所在，在我OR(运筹学)的学习中也有所应用。
#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
deque<LL> q;
LL dp[maxn];
LL a[maxn];
int n,m;
void init(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n ; i++)
scanf("%lld",&a[i]);
q.push_back(0);
}
LL ans = 1e14+10;
void sov(){
for(int i = 1 ; i <= n ; i++){
//printf("i = %d\n",i);
for(auto j:q){
if(j < i-m && i-m >= 0)
q.pop_front();
}
// for(auto j:q){
// printf("inqueue: %d\n",j);
// }
LL k = q.front();
dp[i] = dp[k]+a[i];
while(dp[q.back()]>dp[i]) q.pop_back();
q.push_back(i);
}
for(int i = n-m+1 ; i <= n ; i++){
ans = min(ans,dp[i]);
}
printf("%lld\n",ans);
}
int main(){
init();
sov();
}
