【单调队列】【P2627】修剪草坪

传送门

Wa这次竟然不是Uva的题

Description

在一年前赢得了小镇的最佳草坪比赛后，Farm John变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farm John希望能够再次夺冠。

然而，Farm John的草坪非常脏乱，因此，Farm John只能够让他的奶牛来完成这项工作。Farm John有N只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i。

靠近的奶牛们很熟悉，因此，如果Farm John安排超过K只连续的奶牛，那么，这些奶牛就会罢工去开派对:)。因此，现在Farm John需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。

Input

第一行：空格隔开的两个整数 N 和 K

第二到 N+1 行：第 i+1 行有一个整数 E_i

Output

第一行：一个值，表示 Farm John 可以得到的最大的效率值。

Sample Input

Sample Output

Hint

n≤100000，E在int范围内。

答案可能需要使用long long存储

Solution

看这小东西长得这么别致题长成这样就差不多是个DP了。考虑状态，设计fi为考虑前i头牛的ans。

考虑这么转移：

　　如果选了第i个，那么从i-k-1~i-1个之中就必须不选一个，这样就可以枚举不选的是哪一个，进行转移。

　　状态转移方程为：

　　　　f_i=max{f_j-1+sum_i-sum_j|j>=i-k-1}

　　这么做的时间复杂度为O(nk)，在极端情况下n和k同阶，时间复杂度达到了O(n²)，于是GG。

考虑优化：

　　　　f_i=max{f_j-1+sum_i-sum_j|j>=i-k-1}=sum_i+max{f_j-1-sum_j}

　　因为sum_i是一个常数，所以转移只与j有关。于是就妥妥的单调队列。最终时间复杂度O(n)，可以通过。

Code

#include<cstdio>
#include<algorithm>
#define rg register
#define ci const int
#define cl const long long int

typedef long long int ll;

namespace IO {
    char buf[100];
}

template <typename T>
inline void qr(T &x) {
    char ch=getchar(),lst=' ';
    while(ch>'9'||ch<'0') lst=ch,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(lst=='-') x=-x;
}

template <typename T>
inline void write(T x,const char aft,const bool pt) {
    if(x<0) {putchar('-');x=-x;}
    int top=0;
    do {
        IO::buf[++top]=x%10+'0';
        x/=10;
    }while(x);
    while(top) putchar(IO::buf[top--]);
    if(pt) putchar(aft);
}

template <typename T>
inline T mmax(const T _a,const T _b) {if(_b<_a) return _a;return _b;}
template <typename T>
inline T mmin(const T _a,const T _b) {if(_a>_b) return _b;return _a;}
template <typename T>
inline T mabs(const T _a) {if(_a<0) return -_a;return _a;}

template <typename T>
inline void mswap(T &_a,T &_b) {
    T _temp=_a;_a=_b;_b=_temp;
}

const int maxn  = 100010;

int n,k;
ll frog[maxn];
ll sum[maxn];
ll ans;
int que[maxn];int frt,tal;

int main() {
    qr(n);qr(k);
    for(rg int i=1;i<=n;++i) {ll &now=sum[i];qr(now);now+=sum[i-1];}
    for(rg int i=1;i<=n;++i) {
        if(frt<=tal&&i-que[frt]>k) ++frt;
        rg ll ss=frog[i-1]-sum[i];
        while(frt<=tal&&ss>=frog[que[tal]-1]-sum[que[tal]]) --tal;
        que[++tal]=i;
        if(i<=k) frog[i]=sum[i];
        else frog[i]=sum[i]+frog[que[frt]-1]-sum[que[frt]];
        ans=mmax(ans,frog[i]);
    }
    write(ans,'
',true);
    return 0;
}

Summary

1、方程复杂度太高是可以尝试对方程进行化简，说不定特殊性质就出来了。

2、找到状态难以枚举前面所有元素时，可以考虑枚举特殊点，比如本题中的断点。