继续研究数组分段题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

继续研究数组分段题

继续研究数组分段题# JobHunting - 待字闺中

g*s2011-04-13 07:04

1 楼

正整数的数组x[1..n]，分成k段，找分段法，minimize the maximum sum of any
pieces,
minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
dp:
f(n,k) = min { max { f(i,k-1), sum(x[j]) | i = 1..n, j = i+1..n } }
这个复杂度是O(K*N^2)，可以加速到O(K*NlgN)？
如果输入改成非负整数数组呢？
如果改成任意整数呢？
二分法要求必须是正整数吧？

g*s2011-04-13 07:04

2 楼

非负整数数组 is ok for binary search..

yes if all x[i] are non-negative numbers (integer is not required)
same.
O(K*N*N)
Non-negative numbers can be handled by binary search in O(N*N).
sum(i,j) : sum of (a_i, a_i+1,..,a_j) O(n*n)
sort sum(i,j) O(nlogn)
binary search in the sorted sum(i,j) O( n log n)
Total time is O(n^2)

【在 g*********s 的大作中提到】

: 正整数的数组x[1..n]，分成k段，找分段法，minimize the maximum sum of any
: pieces,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: dp:
: f(n,k) = min { max { f(i,k-1), sum(x[j]) | i = 1..n, j = i+1..n } }
: 这个复杂度是O(K*N^2)，可以加速到O(K*NlgN)？
: 如果输入改成非负整数数组呢？
: 如果改成任意整数呢？
: 二分法要求必须是正整数吧？