继续研究数组分段题# JobHunting - 待字闺中
g*s
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)?
如果输入改成非负整数数组呢?
如果改成任意整数呢?
二分法要求必须是正整数吧?
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)?
如果输入改成非负整数数组呢?
如果改成任意整数呢?
二分法要求必须是正整数吧?