bzoj#P1979. [SPOJ685] SEQPAR
[SPOJ685] SEQPAR
题目描述
有一个长度为 的整数序列 ( 可以为负数)。将它们分成正好 段。设第 段的子序列和为 ()。求一个拆分方法,使 最小。
输入格式
第一行两个整数 。
接下来 个整数,代表 。
输出格式
输出一个数,代表 。
6 3
150
-50
1
101
1
100
101
数据规模与约定
对于 的数据,,。
有一个长度为 n 的整数序列 a1…an(ai 可以为负数)。将它们分成正好 m 段。设第 i 段的子序列和为 si(i∈[1,m])。求一个拆分方法,使 maxi=1m{si} 最小。
第一行两个整数 n,m。
接下来 n 个整数,代表 a1…an。
输出一个数,代表 maxi=1m{si}。
6 3
150
-50
1
101
1
100
101
对于 100% 的数据,1≤m≤n≤104,−104≤ai≤104。