P1792 [国家集训队]种树

    • 584通过
    • 1.5K提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 线性结构 WC/CTSC/集训队
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。

    园林部门得到指令后,初步规划出n个种树的位置,顺时针编号1到n。并且每个位置都有一个美观度Ai,如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳,两棵树决不能种在相邻的位置(i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置!)。

    最终市政府给园林部门提供了m棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上,给出无解信息。

    输入输出格式

    输入格式:

    输入的第一行包含两个正整数n、m。第二行n个整数Ai。

    输出格式:

    输出一个整数,表示最佳植树方案可以得到的美观度。如果无解输出“Error!”,不包含引号。

    输入输出样例

    输入样例#1: 复制
    7 3
    1 2 3 4 5 6 7
    输出样例#1: 复制
    15
    输入样例#2: 复制
    7 4
    1 2 3 4 5 6 7
    
    输出样例#2: 复制
    Error!

    说明

    对于全部数据:m<=n;

    -1000<=Ai<=1000

    N的大小对于不同数据有所不同:

    数据编号 N的大小 数据编号 N的大小
    1 30 11 200
    2 35 12 2007
    3 40 13 2008
    4 45 14 2009
    5 50 15 2010
    6 55 16 2011
    7 60 17 2012
    8 65 18 199999
    9 200 19 199999
    10 200 20 200000
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。