holiday(假期)

　　　　—— 一道妙题(codevs3622)

Description

经过几个月辛勤的工作，FJ 决定让奶牛放假。假期可以在1…N 天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q 天，否则奶牛会玩的腻烦。FJ 想知道奶牛们能获得的最大享受指数。

Input(holiday.in)

第一行：N,P,Q.
第二行：N 个数字，中间用一个空格隔开。

Output(holiday.out)

一个整数，奶牛们能获得的最大享受指数。

Sample Input

5 2 4
-9 -4 -3 8 -6

Sample Output

Limitation

time:1s
memory:65536kb
50% 1≤N≤10000
100% 1≤N≤100000
１<=p<=q<=n

Hint

选择第3-4 天，享受指数为-3+8=5。

explanation

这道题需要仔细想一想，仔细想一想……
首先，我们想一想怎么算每个“几天内”的最大值，首先想可以暴力，枚举一次天数，再枚举一次i，时间是 O(n)，爆了。
所以我们还要想一想。
前缀和？可以优化……
线段树？能考虑……
这几个小想法组合起来就可以了，但是好像不是很好想。
我们可以枚举第一个休息日的编号i，我们要算从这个第i天开始，往后的P到Q天里快乐指数最大那一天快乐指数是多少，枚举过后取个max就行了。
按这种方式算的话，如何将时间复杂度优化到最小？
考虑前缀和和线段树。
前缀和数组pre维护的是的快乐指数之和，线段树求的是i+P-1 ~ i+Q-1这一段区间的快乐指数前缀和最大值maxn,我们发现maxn-pre[i]就是从这个第i天开始，往后的P到Q天里快乐指数最大那一天快乐指数是多少。
其实求最大值的部分，用st表或者其他的也行，只不过我觉得线段树更好。
总共的复杂度就是O(nlogn)。

code

我没开long long，记得写的时候要开。

#include<cstdio>

#include<algorithm>

using namespace std;

int n,mxd,mnd,maxn = -0x3f3f3f3f;

int num[];

int pre[];

int tree[];

void build(int o,int l,int r)

{

    if(l == r)

    {

        tree[o] = pre[l];

        return;

    }

    int mid = (l + r) >> ;

    build(o<<,l,mid);

    build(o<<|,mid+,r);

    tree[o] = max(tree[o<<],tree[o<<|]);

}

int query(int L,int R,int l,int r,int o)

{

    if(L <= l && r <= R)

    {

        return tree[o];

    }

    int mid = (l+r)>>;

    int maximum=;

    if(L <= mid)

        return query(L,R,l,mid,o<<);

    else if(R > mid)

        return query(L,R,mid+,r,o<<|);

    else return max(query(L,R,l,mid,o<<),query(L,R,mid+,r,o<<|));

}

void dokyumento()

{

    freopen("holiday.in","r",stdin);

    freopen("holiday.out","w",stdout);

}

int main()

{

//  dokyumento();

    scanf("%d%d%d",&n,&mnd,&mxd);

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

    {

        scanf("%d",&num[i]);

        pre[i] = pre[i-] + num[i];

    }

    build(,,n);

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

    {

        int ll = i + mnd - ;

        if(ll > n)

            break;

        int rr = (i + mxd -  > n ? n : i + mxd -);

        maxn = max(maxn,query(ll,rr,,n,)-pre[i-]);

    }

    printf("%d",maxn);

    return ;

}

假期

holiday(假期)_题解