洛谷-P2627 修剪草坪

思路

动态规划+单调队列好题。
先考虑使用线性dp。令$dp[i]$表示前$i$头奶牛能得到的最大效率。在第$i$头奶牛，一定在区间$[i-k,i]$内有奶牛$j$得休息。在区间$[i-k,j]$内枚举休息的奶牛，则

$$dp[i]=max(dp[i],dp[i-1]+sum[i]-sum[j])$$

其中$sum[i]$表示前缀和，即奶牛区间$[1,i]$的效率和，$sum[i]-sum[j]$为奶牛区间$[j,i]$的效率和。答案为$dp[n]$。这个方程还是比较容易的吧。
于是我们写出代码，发现只有60分。2个WA，2个TLE。

60分
#include <stdio.h>
#include <iostream>
using namespace std;
int n,k,a[100001],s,dp[100001],sum[100001];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register int i,j;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//前缀和 
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=i-k;j<=i;j++)
		{
			dp[i]=max(dp[i],dp[j-1]+sum[i]-sum[j]);
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

为什么会T呢？因为$n$达到了$10^{5}$。显然$2$层循环会TLE。
我们再仔细思考一下，发现如果想要$dp[i]$尽可能大，不就是想让$dp[j-1]+sum[i]-sum[j]$尽可能大吗？
那我们把方程变形，得：

$$dp[i]=max(dp[i],dp[j-1]-sum[j])+sum[i]$$

此时$(i-k) \leq j \leq i$。
即把$sum[i]$放到外面，这样保证了想让$dp[i]$尽可能大，就只和$j$有关系了，即$max$内的值只和$j$有关。现在只需要用单调队列维护$dp[j-1]-sum[j]$就好了。
按照这个思路，还是60。。WA4个点，发现这题要开long long。。不开long long见祖宗啊。

#include <stdio.h>
#include <iostream>
#include <deque>
#define ll long long int
using namespace std;
ll n,k,a[100001],s,dp[100001],sum[100001];
struct node
{
	ll v,position;//v为权，position是下标 
};
deque<node> dq;
inline void update(ll i)
{
	ll x(dp[i-1]-sum[i]);//维护dp[j-1]-sum[j] 
	while(!dq.empty() && dq.back().v<=x) dq.pop_back();//如果队尾小于dp[j-1]-sum[j]，全扔掉 
	dq.push_back({x,i});//新元素放进去 
	
}
inline ll query(ll i)
{
	while(!dq.empty() && dq.front().position<i-k) dq.pop_front();//检查是否在区间[i-k,i]内 
	return dq.front().v;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register ll i,j;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//前缀和 
	}
	dq.push_back({0,0});//先压一个元素 
	for(i=1;i<=n;i++)
	{
		update(i);
		dp[i]=query(i)+sum[i];//dp[i]=max(dp[i],dp[j-1]-sum[j])+sum[i]
	}
	cout<<dp[n]<<endl;
	return 0;
}