dp例题 or 水题

先说下题意吧，题面给的题意我都看不懂：

有\(n\)本书，每本书有一个页数%a_i%。每个人能写连续的几本书，他们写书的速度可以认为是1页1天。求让\(k\)个人抄完这\(n\)本书的最短时间。

PS：\(k\)个人抄书的时间是其中抄的最慢的人用的时间。

dp的状态非常容易想：dp[i][j]表示前\(i\)本书，用\(j\)个人抄的最短时间。

那么显然可以枚举一个小于\(i\)的\(j\)来更新状态，这个方程式很水就不讲了。

重点在于输出方案。

得到的最短时间，根据题意，我们要让后面的人尽可能的抄更多的书。

做法很简单，从后面开始递归，枚举出最大的一段满足的区间供给那个人抄，然后剩下的区间就给剩下的人抄。

代码：

#include
    
     #include
     
      #include
      
       const int maxn = 505;int dp[maxn][maxn];int a[maxn], b[maxn];int n, m;void print(int maxv, int pos){    if(pos == 0) return;    int sum = 0;    int i;    for(i = pos; i >= 1; i--)    {        sum += a[i];        if(sum > maxv) break;    }    i++;    print(maxv, i - 1);    printf("%d %d\n", i, pos);}int main(){    memset(dp, 0x3f, sizeof dp);    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++)    {        scanf("%d", &a[i]);        b[i] = b[i - 1] + a[i];    }    for(int i = 1; i <= n; i++) dp[i][1] = b[i];    /*    for(int k = 2; k <= m; k++)    {        for(int i = 2; i <= n; i++)        {            for(int j = 1; j < i; j++)            {                dp[i][k] = std::min(dp[i][k], std::max(dp[j][k - 1], a[i] - a[j]));            }        }    }    */    for(int i = 2; i <= n; i++)    {        for(int j = 1; j < i; j++)        {            for(int k = 2; k <= m; k++)            {                dp[i][k] = std::min(dp[i][k], std::max(dp[j][k - 1], b[i] - b[j]));            }        }    }    //printf("%d\n", dp[n][m]);    print(dp[n][m], n);    return 0;}