7487-烽火传递

题目传送
思考方向
设$dp[i]$表示第$i$个烽火台发信号所需要的最小代价，注意第$i$烽火台是要发射信号的。
考虑转移：第$i$个烽火台由前面[i-m,i-1]范围内的烽火台转移而来，这样才能保证连续$m$个烽火台中至少有一个发射信号，为了使得$dp[i]$最优，必然要在[i-m,i-1]范围内找到最优(代价最少)的子问题，也就是$i$前面的$m$个状态中寻找最优的状态，显然符合单调队列特性。

	head = 0, tail = 0;
	for(int i = 1; i <= n; ++i){
		dp[i] = q[head] + a[i]; //状态转移
		while(head<=tail && i - pos[head] > m - 1) ++head; //区间范围外的出队
		while(head<=tail && q[tail]>=dp[i]) --tail; //调整队列单调性
		q[++tail] = dp[i]; //入队
		pos[tail] = i;
	}

首先计算出$dp[i]$，其次队列的头和即将入队的$dp[i]$的距离调整为$m-1$，然后把$dp[i]$放入队列中，使得单调队列的头和尾的距离为$m$，相当于区间$[i-m+1,i]$的单调队列维护完成，为下一次转移做准备。
最后，枚举$n-m+1$~$n$范围内的子问题。为什么至少从$n-m+1$开始，因为这个位置能保证传到最后，再往前的位置不能保证传到最后，或者说最后$m$个状态能覆盖完烽火台。
小结
这题比较典型的单调队列DP优化，原本的$DP$，都是从之前的状态中，寻找一个最优的状态往往需要通过枚举寻找。而符合单调队列特性的$DP$，直接从符合的决策集（单调队列）中找队头就可以了，省去了一些无效枚举。