P1484 种树

    • 1.2K通过
    • 4.4K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    cyrcyr今天在种树,他在一条直线上挖了n个坑。这n个坑都可以种树,但为了保证每一棵树都有充足的养料,cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够,他至多会种k棵树。假设cyrcyr有某种神能力,能预知自己在某个坑种树的获利会是多少(可能为负),请你帮助他计算出他的最大获利。

    输入输出格式

    输入格式:

    第一行,两个正整数n,k。

    第二行,n个正整数,第i个数表示在直线上从左往右数第i个坑种树的获利。

    输出格式:

    输出1个数,表示cyrcyr种树的最大获利。

    输入输出样例

    输入样例#1: 复制
    6 3 
    100 1 -1 100 1 -1
    
    输出样例#1: 复制
    200

    说明

    对于20%的数据,n<=20。

    对于50%的数据,n<=6000。

    对于100%的数据,n<=500000,k<=n/2,在一个地方种树获利的绝对值在1000000以内。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。