1599：【 例 3】修剪草坪

时间限制: 1000 ms         内存限制: 524288 KB

【题目描述】

原题来自：USACO 2011 Open Gold

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

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

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

【输入】

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

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

【输出】

一行一个值，表示 FJ 可以得到的最大的效率值。

【输入样例】

5 2
1
2
3
4
5

【输出样例】

12

【提示】

样例说明:

FJ 有 5 只奶牛，他们的效率为 1,2,3,4,5。他们希望选取效率总和最大的奶牛，但是他不能选取超过 2 只连续的奶牛。FJ 选择出了第三只以外的其他奶牛，总的效率为 1+2+4+5=12。

数据范围与提示：

对于全部数据，1≤N≤10⁵,0≤Ei≤10⁹ 。

 

sol：

用S[i]表示前缀和

考虑dp[i][0,1]表示到第i个牛（是否工作）的最大效率和

dp[i][0]=max(dp[i-1][0],dp[i-1][1])

dp[i][1]=max(dp[x][0]+S[i]-S[x]);(i-m≤x<i)

dp[i][1]可以用单调队列优化，维护队首为dp[i][0]-S[i]最大的单调队列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-');
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
inline void writeln(ll x)
{
    write(x);
    putchar('\n');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) writeln(x)
const int N=100005;
int n,m;
ll dp[N][2],Qzh[N];
struct Dd_Queue
{
    ll Shuz;
    int Weiz;
}Ddq[N];
int main()
{
    int i,Head=0,Tail=0;
    R(n); R(m);
    for(i=1;i<=n;i++)
    {
        int x=read(); Qzh[i]=Qzh[i-1]+x;
        dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
        while(Head<Tail&&Ddq[Head].Weiz<i-m) Head++;
        dp[i][1]=dp[Ddq[Head].Weiz][0]+(Qzh[i]-Ddq[Head].Shuz);
        while(Head<=Tail&&dp[i][0]-Qzh[i]>dp[Ddq[Tail].Weiz][0]-Ddq[Tail].Shuz) Tail--;
        Ddq[++Tail]=(Dd_Queue){Qzh[i],i};
    }
    Wl(max(dp[n][0],dp[n][1]));
    return 0;
}
/*
input
5 2
1 2 3 4 5
output
12
*/

View Code