2697-修建草坪

题目传送
思考方向
题目要求区间长度不超过$k$的前提下，效率之和达到最大。反过来想一下就是在长度$k$区间内去掉一个最小的，不过这个贪心策略会失败。
比如样例：1 2 3 4 5
按照贪心策略，第一个区间中选择1，然后2和3保留，接下来选4，保留5，最终效率之和为10。
而答案为12，即3不保留，其他都保留。
所以不把所有情况枚举一遍，无法确定最优。
假设$dp[i]$表示不选取奶牛$i$后的最小值之和，那么有效区间$[i-k,i-1]$中找一个最小值之和。

观察上图，在区间$[i-k,i-1]$内寻找不选取的最小和的点跟$i$这个点组合，能使得剩下的区间长度不会超过$k$。
如果用枚举，$k$如果大一点，显然超时，要在区间内找最小的，显然单调队列更好,能够马上找出最优的。
只要在区间范围内，队列中的某个决策可能会被使用多次，这就具备了最优子结构。
子问题一旦构造出来了，现在思考一下状态转移方程，单调队列DP优化跟区间有关，所以：
$dp[i]=a[i]+min(dp[j]),i-k<=j<=i-1$
即第$i$只奶牛不选，那么前面所有合法区间内的子问题中转移一个最优的过来（值最小）。

	for(int i = 1; i <= n; i++){
		dp[i] = q[head]+cow[i]; //转移：计算出当前第i个不放入的最小值之和
		while(head <= tail && i - pos[head] > k) ++head; //区间外的出队
		while(head <= tail && q[tail] >= dp[i]) --tail; //调整队列单调性
		q[++tail] = dp[i]; 
		pos[tail] = i;
	}

最后，在$dp$数组中，寻找代价最小的解。需要注意的是，应该从$n-k$位置开始枚举，直到$n$。因为至少在第$n-k$个位置，这样才能使得剩下的奶牛不会超过$k$头。

long long ans = 2e18;
for(int i = n-k; i <= n; ++i) ans = min(ans, dp[i]);
cout << sum - ans << "\n";  //sum为整个序列的总和