先定义一下数组，f[i][j]表示第i个人，抄了j本书花的最短时间。 w[i][j]表示[i,j]闭区间内，从第i本书抄到第j本书用的时间； 转移方程：f[h][i]=min(f[h][i],max(f[h-1][j],w[j+1][i])); （1<=i<=m,1<=j<=i-1） 求出最小花费时间后，题目要求输出方案，且让后面的人尽量多抄。 用贪心就可以了，从后面开始，只要当前这个人时间不到最佳时间，就一直让他抄，就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #define M 2000000000 using namespace std; int f[501][501]; int m,k,a[501]; int w[501][501],l[501],r[501]; int main() { memset(f,127,sizeof(f)); scanf("%d%d",&m,&k); for(int i=1;i<=m;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { w[i][i]=a[i]; for(int j=i;j<=m;j++) { w[i][j]=w[i][j-1]+a[j]; } f[1][i]=w[1][i]; } for(int h=2;h<=k;h++) { for(int i=1;i<=m;i++) { for(int j=1;j<=i-1;j++) { f[h][i]=min(f[h][i],max(f[h-1][j],w[j+1][i]));//转移方程 } } } int p=f[k][m],ll=m; for(int i=k;i>=1;i--)//贪心一下 { int u=0,rr=ll; while(u+a[ll]<=p&&ll>=1) { u+=a[ll]; ll--; } l[i]=ll+1; r[i]=rr; } for(int i=1;i<=k;i++) printf("%d %d\n",l[i],r[i]); return 0; }