437. 书籍复印
题目
描述 给定 n 本书, 第 i 本书的页数为 pages[i]. 现在有 k 个人来复印这些书籍, 而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages[0], pages[1], pages[2], 但是不可以只复印 pages[0], pages[2], pages[3] 而不复印 pages[1].
所有人复印的速度是一样的, 复印一页需要花费一分钟, 并且所有人同时开始复印. 怎样分配这 k 个人的任务, 使得这 n 本书能够被尽快复印完?
返回完成复印任务最少需要的分钟数.
来源:https://www.lintcode.com/problem/copy-books/description
思路
代码
public static int copyBooks(int[] pages
, int k
) {
int n
= pages
.length
;
if(n
==0){
return 0;
}
int[][] f
= new int[k
+1][n
+1];
int[] S
= new int[n
];
S
[0] = pages
[0];
for(int i
=1;i
<n
;i
++){
S
[i
] = S
[i
-1]+pages
[i
];
}
for(int i
=1;i
<=k
;i
++){
for(int j
=0;j
<=n
;j
++){
if(j
==0){
f
[i
][j
] = 0;
}else if(j
==1){
f
[i
][j
] = pages
[j
-1];
}else{
if(i
==1){
f
[i
][j
] = S
[j
-1];
}else{
int m
= Integer
.MAX_VALUE
;
for(int l
=1;l
<=j
;l
++){
int t
= Math
.max(f
[i
-1][l
-1],S
[j
-1]-S
[l
-1]+pages
[l
-1]);
m
= m
>t
?t
:m
;
}
f
[i
][j
] = m
;
}
}
}
}
return f
[k
][n
];
