题目详见:https://www.luogu.org/problem/show?pid=1281 本题有两种解法: 一.动态规划 类似于乘积最大那道题,关键是划分好书的分配方式,因为书本抄写是连续的,因此该问题是满足无后效性的,我们可以以抄书的人数为阶段,dp[i][j]表示前i个人抄写j本书需要抄写所消耗的最少时间. 动态规划转移方程为:dp[i][j] = min(dp[i][j],max(dp[i-1][k],s[j] - s[k]));其中1 <= k < j,s数组是前缀和, s[i]代表从1至i本书的页数和. 具体实现见代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,m; int book[505],s[505]; int dp[505][505]; //dp[i][j]代表前j本书由i个人复制的最优值 int ans[505][3]; //ans[i][1]用来存第i个人复制书稿的起点，ans[i][2]用来存第i个人复制书稿的终点。 void cal(int x) { int t = x, start,end = n; int k=n; for(int i = 1,j = m; i <= m; i++,j--) { ans[j][2] = end; t = x; while(t-book[k] >=0 && k > 0) { t -= book[k]; k--; } ans[j][1] = k+1; end = k; } } int main() { memset(dp,0x7f,sizeof(dp)); cin >> n >> m; for(int i = 1; i<= n; i++) { cin >> book[i]; s[i] = s[i-1] + book[i]; dp[1][i] = s[i]; } for(int i = 2; i<= m; i++) { for(int j = 1; j<= n; j++) { int temp; for(int k = 1; k < j; k++) { temp = max(dp[i-1][k] , s[j] - s[k]); dp[i][j] = min(dp[i][j],temp); } } } cal(dp[m][n]); for(int i = 1; i <= m; i++) { cout << ans[i][1] <<" " << ans[i][2] << endl; } return 0; }二.二分答案 从题目可以分析,这道题的解一定是在1 ~ 所有书本的页数和s 之间,它们是线性且有序的,因些我们可以二分答案来解这道题.如果二分的mid能让抄书人从后向前分给m个人抄写能分得下,则让继续搜索左区间，继续寻找更小的值，如果m个人抄写还不够，则说明这个mid小了，需要搜索右区间。 具体代码见下面：
#include<iostream> using namespace std; int n,m; int book[505],s[505],ans[505][3],le,ri; int pd(int x) { int k = m,i = n,res = x; while(k > 0) { res = x; ans[k][2] = i; while(i>0 && res - book[i] >= 0) { res -= book[i]; i --; } ans[k][1] = i+1; k--; } if( i > 0) return false; else return true; } void calAns(int x) { int k = m,i = n,res = x; while(k > 0) { res = x; ans[k][2] = i; while(i>0 && res - book[i] >= 0) { res -= book[i]; i --; } ans[k][1] = i+1; k--; } } int main() { cin >> n >> m; for(int i = 1; i<= n; i++) { cin >> book[i]; s[i] = s[i-1] + book[i]; } le = 0;ri = s[n] +1; while(le+1 < ri) { int mid = le + (ri - le)/2; if(pd(mid)) { ri = mid; } else le = mid; } calAns(ri) ; for(int i = 1; i<= m; i++) { cout << ans[i][1] << " " << ans[i][2] << endl; } return 0; }