题解

1 条题解

  • 0
    @ 2020-09-24 07:45:02

    题目大意:

    在一年前赢得了小镇的最佳草坪比赛后,FJ变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,FJ希望能够再次夺冠。
    然而,FJ的草坪非常脏乱,因此,FJ只能够让他的奶牛来完成这项工作。FJ有N(1 <= N <= 100,000)只排成一排的奶牛,编号为1...N。

    每只奶牛的效率是不同的,奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。
    靠近的奶牛们很熟悉,因此,如果FJ安排超过K只连续的奶牛,那么,这些奶牛就会罢工去开派对:)。

    因此,现在FJ需要你的帮助,计算FJ可以得到的最大效率,并且该方案中没有连续的超过K只奶牛。

    solution:

    f[i]=min{f[j]}+a[i]

    f[i]表示前i头奶牛满足条件且不用第i头奶牛的最少损失

    res=总收益-最少损失

    单调队列

  • 1

信息

ID
2154
难度
9
分类
动态规划 | 数据结构 | 单调队列 点击显示
标签
递交数
5
已通过
1
通过率
20%
被复制
2
上传者