題目如下： 給出一個數組A包含n個元素，表示n本書以及各自的頁數。現在有個k個人復印書籍，每個人只能復印連續一段編號的書，比如A[1],A[2]由第一個人復印，但是不能A[1],A[3]由第一個人復印，求最少需要的時間復印所有書。
樣例： A = [3,2,4],k = 2
返回5，第一個人復印前兩本書
解題思路： 這個題有一定難度，先提出合理假設B（l，k）為l個數據規模的k人分配使用最短時間。把數據規模劃分為兩部分，從右到左，依次增加右規模，表示第k人印刷書籍量，而左規模則表示其他人所印刷書籍量，這樣左規模的最短時間即是B（左規模數量，k-1）了，至于右規模的最短時間，用相應B（右規模數量，1）-B（左規模數量，1）即可，把當前規模的右規模從l到k（如果有k個人印k本書，一人一本肯定最短時間，因此預留k本書）的所有最短時間取最小值，即當前規模最小時間。那么，只需要提供k-1人的1到l數據規模的最短時間即可遞推B（l，k）。
思路實現代碼：
int Method(int *n,int len,int k){ if(k>len) k=len; int **matrix=new int *[len]; for(int i=0;i<len;++i) matrix[i]=new int[k+1], ZeroMemory(matrix[i],k*4+4); int res=0; matrix[0][1]=n[0]; for(int i=1;i<len;++i) matrix[i][1]=matrix[i-1][1]+n[i]; for(int i=2;i<=k;++i) for(int p=i-1;p<len;++p) for(int t=i-1;t<=p;++t) { res=max(matrix[t-1][i-1], matrix[p][1]-matrix[t-1][1]); matrix[p][i]=matrix[p][i]==0?res:min(matrix[p][i],res); } res=matrix[len-1][k]; for(int i=0;i<len;++i) delete[] matrix[i]; delete[] matrix; return res;}新聞熱點
疑難解答
