一本通1599【 例 3】修剪草坪

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≤105,0≤Ei≤109

 

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]最大的单调队列

一本通1599【 例 3】修剪草坪
#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
上一篇:一本通1593【例 2】牧场的安排


下一篇:cocos2d-x 利用CCLabelTTF制作文字描边与阴影效果的实现方法