TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2914
  • 题目
  • P2914nodgd参加APIO
    限制 : 时间限制 : 15000 MS   空间限制 : 165536 KB
    问题描述

    题目背景
    nodgd正在APIO赛场上努力的A题。他按照以往的做法,先把所有题都看一遍,再选自己觉得最好做的题先做。nodgd觉得第二题是最容易上手的,这道题是这样描述的:一开始给你一个长度为N的非负整数序列,你需要把它砍断分成M段,那么这一分割方案的得分为......
    给你这个序列以及正整数M,你需要求出最大的得分,并输出任意一个得到这个分数的方案。
       看完题,nodgd又犯了老毛病,也就是考试的时候浮想联翩。他觉得这个题还不够有趣,于是决定修改一下题目。
    题目描述
       将长度为N的非负整数序列分成M段,从左往右编号1到M,其中的编号为k的一段至少要有k个数,该段的得分为其中最大的一个数的值。总的得分就是这M个段的得分总和,请你求出最大的总分。
       nodgd觉得这是一道不错的题目,于是就丧心病狂把它拿来当成高一同学的月赛题了……考虑到是高一同学,需要以鼓励和学习为主,所以nodgd把数据范围设置得比较小,并且不需要你输出方案。

    输入格式

    第一行两个正整数N,M,表示序列的长度以及你需要分割成的块数。
    接下来N行每行一个数,为这个序列。

    输出格式

    只需要输出一个数,表示你能够获得的最大得分。

    样例输入

    样例输入1:
    3 2
    1 2 3

    样例输入2:
    10 3
    9 8 7 6 5 4 3 2 1 0

    样例输出

    样例输出1:
    4

    样例输出2:
    23

    提示

    样例解释1:
    只有唯一的分割方案,即第一段为{1},得分为1;第二段为{2,3},得分为3。所以总得分为4。

    样例解释2:
    分成{9},{8,7},{6,5,4,3,2,1,0},得分为9+8+6=23。没有比这更优的分割方案。
    数据范围:
    对于20%的数据,N≤20
    对于40%的数据,N≤100
    对于60%的数据,N≤500
    对于100%的数据,N≤100000,2≤M≤20,0≤序列中每个数≤1000


    来源  感谢nodgd出题