1. 题目

传送门＝￣ω￣＝

2. 题解

其实。。。很水的一道题。。。（kb 老早就AC了）
我们把问题分开。
我们首先不设计方案，只求最小的时间。
设 $f(i,j)$为给你 $i$本书和 $j$个人时的最短时间。
设 $sum[i]$为前 $i$本书的页数之和（即前缀和）。
递推式：
$f(i,j)=max\{f(x,j-1),sum[i]-sum[x]|j-1<=x<=i-1\}$

然后我们推算出最小时间后，用贪心算法，$O(m)$求出答案。

代码：

#include <bits/stdc++.h>
using namespace std;
int m,k,sum[505],f[505][505],ans,pos[505][2];
int dfs(int c,int p)
{
    if(f[c][p]!=INT_MAX)return f[c][p];
    if(p==1)return f[c][p]=sum[c];
    for(int i=p-1;i<=c-1;i++)f[c][p]=min(f[c][p],max(dfs(i,p-1),sum[c]-sum[i]));
    return f[c][p];
}
int main()
{
    scanf("%d%d",&m,&k);
    for(int i=1;i<=m;i++)for(int j=1;j<=k;j++)f[i][j]=INT_MAX;
    for(int i=1,a;i<=m;i++)scanf("%d",&a),sum[i]=sum[i-1]+a;
    ans=dfs(m,k),pos[1][0]=pos[1][1]=m;
    for(int i=1;i<=k;i++)
    {
        while(sum[pos[i][1]]-sum[pos[i][0]-1]<=ans&&pos[i][0])pos[i][0]--;
        pos[i+1][0]=pos[i+1][1]=pos[i][0]++;
    }
    for(int i=k;i>=1;i--)printf("%d %d\n",pos[i][0],pos[i][1]);
    return 0;
}