题目的大意就是给定一个长度为n的序列，求出这个序列中长度不超过m的子串的最大和

很容易想出的一个解法就是枚举起点终点，直接暴力扫一遍得出答案。

当然也很容易发现这种做法肯定会TLE。

也有一个很容易想到的优化方法——利用前缀和。

但是我们会发现即便如此，还是会TLE。

也就是说枚举这条路看起来走不通的样子……

那么我们换一个思路

依然是利用前缀和的思想，首先观察部分和的公式：

sum[i~j]=sum[j]-s[i-1]。

如果我们目标区间内使被减数尽可能大，减数尽可能小，就可以保证sum[i~j]最大。

同时维护被减数最大减数最小好像比较麻烦……

那么我们可以换一个方向思考：

维护一个动区间内的最小减数，然后枚举被减数即可

什么样的数据结构可以满足这样的操作呢？

很明显，线段树单调队列可以做到。

Code time：

//其实可以手写一个单调队列，但是最近学习一些有关类的知识就顺便练练手了。

//代码还是很好懂的，即使没学过应该也能轻松看懂

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

class queue

{

    int x[5000005],head,tail;

public:

    void set()

    {

        head=1;

        tail=1;

        memset(x,0,sizeof(x));

    }

    void push_back(int y)

    {

        x[tail++]=y;

    }

    void pop_front()

    {

        head++;

    }

    bool empty()

    {

        return head==tail;

    }

    void pop_back()

    {

        tail--;

    }

    int back()

    {

        return x[tail-1];

    }

    int front()

    {

        return x[head];

    }

    //由于stl自带的queue只支持队头弹出，deque又不会用，于是手写了一个类。

    //(大概算是面向对象编程的首次尝试？)

}que;

int n,m,a,sum[500005],ans;

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)

    {

        scanf("%d",&a);

        sum[i]=sum[i-1]+a;//前缀和预处理

    }

    que.set();

    for (int i=1;i<=n;i++)

    {

        while (sum[que.back()]>sum[i]&&!que.empty()) que.pop_back();

        que.push_back(i);

        if (i-que.front()>m&&!que.empty()) que.pop_front();

        ans=max(ans,sum[i]-sum[que.front()]);

    }//单调队列基本操作

    printf("%d",ans);

    return 0;

}

巴特西

【Luogu P1714】切蛋糕（面向对象编程首次尝试？）

很明显，线段树单调队列可以做到。

最新文章

热门文章