#LGP1182. 数列分段 Section II
数列分段 Section II
题目描述
对于给定的一个长度为 的正整数数列 ,现要将其分成 ()段,并要求每段连续,且每段和的最大值最小。
关于最大值最小:
例如一数列 要分成 段。
将其如下分段:
第一段和为 ,第 段和为 ,第 段和为 ,和最大值为 。
将其如下分段:
第一段和为 ,第 段和为 ,第 段和为 ,和最大值为 。
并且无论如何分段,最大值不会小于 。
所以可以得到要将数列 要分成 段,每段和的最大值最小为 。
输入格式
第 行包含两个正整数 。
第 行包含 个空格隔开的非负整数 ,含义如题目所述。
输出格式
一个正整数,即每段和最大值最小为多少。
样例 1
5 3
4 2 4 5 1
6
说明 / 提示
对于 的数据,。
对于 的数据,。
对于 的数据,,,, 答案不超过 。
来源:洛谷 P1182。题面及样例来自洛谷公开题库导出,保留原题署名。
本题在 Turing OJ 内提交评测;测试数据由本站独立构造,并非洛谷原始测试点。