LOJ #10176. 「一本通 5.5 例 2」最大连续和

用前缀和预处理,用单调队列维护[i-m,i]区间内前缀和的最小值。

实际上求和区间是[i-m+1,i],但是这个区间内的和用sum数组表示为sum[i]-sum[i-m],
即把sum的区间看成[i-m,i],滑动窗口长度为m+1。

每次遍历的区间内所有元素和的最大值为sum[i]-sum[q.front()],找出sum[i]-sum[q.front()]的最大值即可。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10,inf=(1<<31)-1;
int n,m,mx,x,sum[N];
deque<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    mx=-inf;
    for(int i=0;i<=n;i++)//i从0开始
    {
        while(!q.empty()&&i-q.front()>=m+1)q.pop_front();//弹出旧区间的点
        if(!q.empty())mx=max(mx,sum[i]-sum[q.front()]);//取最大值的位置放在第一个while后面
        while(!q.empty()&&sum[i]<sum[q.back()])q.pop_back();//维护,使队列单调
        q.push_back(i);
    }
    printf("%d\n",mx);
    return 0;
}

LOJ #10177. 「一本通 5.5 例 3」修剪草坪

使总效率最大 即 使损失的效率最小(损失即奶牛可以休息),设dp[i]表示以i为结尾的损失的最小效率,用单调队列维护dp数组。

滑动窗口的长度是k+2,因为最多k个连续的点,再加上左右各一个可以休息的点,总共长度k+2,并保证其队首对应dp值为最小值。

然后找出[n-k,n]中的最小dp值mi,sum-mi即为答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
deque<int>q;
ll n,k,x,mi,sum,a[N],dp[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum+=a[i];
    for(int i=0;i<=n;i++)
    {
        while(!q.empty()&&i-q.front()>=k+2)q.pop_front();
        if(!q.empty())dp[i]=dp[q.front()]+a[i];
        while(!q.empty()&&dp[i]<dp[q.back()])q.pop_back();
        q.push_back(i);
    }
    mi=((ll)1<<63)-1;//不要写成0x3f3f3f3f,因为dp最大值可能达到long long的最大值
    for(int i=n-k;i<=n;i++)
        mi=min(mi,dp[i]);
    printf("%lld\n",sum-mi);
    return 0;
}