Example
Given array A =
[3,2,4]
, k = 2
.
Return
5
( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )
很明显地用dp来做。dp[i][j] 代表前i本书由j个工作者完成需要的最小时间。状态转移方程如下:
dp[i+1][j+1] = Min(Max(dp[i][k], A[k]+...+A[j+1])), where k from i to j+1
意思就是每加入一个新worker的时候,从后往前累加他需要copy的book,每次更新总体所需要的时间;而总体需要的时间是之前所有worker分配方案中的最优时间和新worker所需时间两者中的较大值。
时间复杂度 O(N^2*k), 暂时没想到 O(N*k) 的方法 :( 麻烦各路大神指点。。。
O(n * k) solution http://sidbai.github.io/2015/07/25/Copy-Books/
ReplyDeletedp[i][j] 代表前j本书由i个工作者完成需要的最小时间?
ReplyDelete我觉得是的
DeleteThis comment has been removed by the author.
ReplyDeletedp[i][j] 应该表示的是 前 j 本书 由 i 个工作者完成所需最小时间
ReplyDelete