g*********s
发帖数: 1782 | 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***s
发帖数: 3811 | 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)？
: 如果输入改成非负整数数组呢？
: 如果改成任意整数呢？
: 二分法要求必须是正整数吧？
|
|
