时间限制: 1000 ms 内存限制: 524288 KB
原题来自：NOIP 2010 提高组初赛 · 完善程序
烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。
在某两个城市之间有 n 座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 m 个烽火台中至少要有一个发出信号。现在输入 n,m 和每个烽火台的代价，请计算总共最少的代价在两城市之间来准确传递情报。
第一行是 n,m，表示 n 个烽火台和连续烽火台数 m；
第二行 n 个整数表示每个烽火台的代价 ai 。
输出仅一个整数，表示最小代价。
5 3
1 2 5 6 2
4
样例说明
在第 2,5 号烽火台上发信号。
数据范围与提示：
对于全部数据，1≤n,m≤2×105,1≤ai≤1000。
sol：dp[i]表示强制选i这个位置时1~i的最小代价，dp[i]=min（dp[i-m]~dp[i-1]）+ a[i]
min（dp[i-m]~dp[i-1]）可以方便的用单调队列优化，所以复杂度就变成O（n）了
答案就是min（dp[n-m+1]~dp[n]）
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } inline void writeln(ll x) { write(x); putchar(‘\n‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) writeln(x) const int N=200005,inf=0x3f3f3f3f; int n,m,a[N],dp[N]; struct Record { int Shuz,Weiz; }Ddq[N]; int main() { int i,Head=1,Tail=0; R(n); R(m); for(i=1;i<=n;i++) R(a[i]); memset(dp,63,sizeof dp); for(i=1;i<=m;i++) { while(Head<Tail&&Ddq[Head].Weiz<i-m) Head++; dp[i]=a[i]; while(Head<=Tail&&Ddq[Tail].Shuz>dp[i]) Tail--; Ddq[++Tail]=(Record){dp[i],i}; } for(i=m+1;i<=n;i++) { while(Head<Tail&&Ddq[Head].Weiz<i-m) Head++; dp[i]=Ddq[Head].Shuz+a[i]; while(Head<=Tail&&Ddq[Tail].Shuz>dp[i]) Tail--; Ddq[++Tail]=(Record){dp[i],i}; } int ans=inf; for(i=n-m+1;i<=n;i++) { ans=min(ans,dp[i]); } Wl(ans); return 0; } /* input 5 3 1 2 5 6 2 output 4 */
原文：https://www.cnblogs.com/gaojunonly1/p/10372074.html
