[文章目录]
Description
在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定代价。为了使情报准确地传递，在连续m个烽火台中至少要有一个发出信号。请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。
单调队列优化DP，原来想法是以能覆盖到第几个为状态，循环点；但是时间是n*m的，因为每个点都要维护和其相连的f[]；后来改变状态，f[i]表示选第i个点时的最小体力，这样的话，状态之间的关系就是对于每一个点x，他前面[i-m,i-1]的点至少有一个得选，所以，用单调队列维护这个区间的最小值，每次直接用，作为新的f[]；然后再更新单调队列，进行DP。
注意的是：que[]里存的是第几个点，并不是最小体力，以便于判断区间是否已经掠过该点
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
int val[101000];
long long f[101000];
int que[101000];
int head=1,tail=1;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
for(int i=1;i<=n;i++)
{
f[i]=f[que[head]]+val[i];
while(tail>=head&&f[i]<=f[que[tail]])
tail--;
que[++tail]=i;
while(que[head]<i+1-m)
head++;
}
printf("%lld",f[que[head]]);
return 0;
}好难QAQ，做了1.5h，感觉自己好弱智！！！