烽火传递 描述
烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递。
输入格式
第一行有两个数n,m分别表示n个烽火台，在m个烽火台中至少要有一个发出信号。 第二行为n个数，表示每一个烽火台的代价。
输出格式
一个数，即最小代价。
测试样例1
输入
5 3 1 2 5 6 2 输出
4
#include <iostream> #include <cstring> #include <cstdio> #define INF 2100000000 using namespace std; const int maxn = 1e5+5; int n,m; int w[maxn],f[maxn],q[maxn]; int main() { freopen("fhcd.in","r",stdin); freopen("fhcd.out","w",stdout); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&w[i]); int st = 1, en = 1; q[1] = f[0] = 0; for(int i = 1; i <= n; i++) { while(i-q[st] > m) st++; f[i] = f[q[st]]+w[i]; while(f[q[en]] >= f[i]) en--; q[++en] = i; } int ans = INF; for(int i = n; i >= n-m+1; i--) ans = min(ans, f[i]); printf("%d\n",ans); return 0; }