http://poj.org/problem?id=1505

Idea

考察第i个人复制前j本书的最小完成时间数.设前面t本书由前i-1人抄写,而t+1,t+2,…j本书由第i人抄写
可以得到状态转移方程Poj 1505 - 图1
初始时,Poj 1505 - 图2Poj 1505 - 图3.

这样我们就可以得到最短抄写时间Poj 1505 - 图4。

接着我们从后往前遍历 书的页数数组 设置一个累加器sum 当sum的值大于最短抄写时间时。
该位置即为分割点

Code

  2. import java.util.Scanner;
  4. public class Main {
  5.     //dp状态转移方程： 方程 : dp[i][j] = min(dp[i][j], max(dp[i-1][v], sum[j]-sum[v])) i 个人 抄写 前j 本书的最少时间
  6.     //破题思路： 先根据dp方程清楚dp[m][k]的最少时间
  7.     //在从后往前遍历页数数组 累加和sum 如果sum>dp[m][k]  则找到分割点
  8.     public static void main(String[] args)  {
  9.         Scanner scanner=new Scanner(System.in);
  10.         int a,b,c;
  11.         int[] d=new int[520]; //页数数组
  12.         int[][] dp=new int[520][520]; //dp数组
  13.         int[] sum=new int[520]; //存储a[1]到a[i-1]的累加和 java会自动把数组置零
  14.         int[] path=new int[520]; //存储答案路径
  15.          a=scanner.nextInt();
  16.         for(int i=0;i<a;i++)
  17.         {
  18.             b=scanner.nextInt();
  19.             c=scanner.nextInt();
  20.             for(int j=0;j<=c;j++)
  21.             {
  22.                 for(int k=0;k<=b;k++)
  23.                 {
  24.                     dp[j][k]=Integer.MAX_VALUE;
  25.                 }
  26.             }
  27.             for(int j=1;j<=b;j++)
  28.             {
  29.                 d[j]=scanner.nextInt();
  30.                 sum[j]+=sum[j-1]+d[j];
  31.                 dp[1][j]=sum[j];  //一个人抄写的时间就是累加和
  32.             }
  33.             for(int j=2;j<=c;j++)   //c个人 其实dp[1][j]已经被初始化
  34.             {
  35.                 for(int k=j;k<=b;k++)  //j个人至少要抄写j本书
  36.                 {
  37.                     for(int v=j-1;v<k;v++)
  38.                     /*v=1的时候 就是 就是前2-1个人抄写1，2,3，。。。本书
  39.                     v=2的时候 就是前3-1个人 抄写2，3，。。。。本书
  40.                     j-1个人至少要抄写j-1 到k-1本书
  41.                      */
  42.                     {
  43.                         if(dp[j][k]>Math.max(dp[j-1][v],sum[k]-sum[v]))
  44.                             dp[j][k]=Math.max(dp[j-1][v],sum[k]-sum[v]);
  45.                     }
  46.                 }
  47.             }
  48.             int result=dp[c][b];
  49.             int sum1=0;
  50.             for(int j=b,k=c-1; j>=1;j--)    //c个人必定有c-1个分割点
  51.             {
  52.                 sum1+=d[j]; //从后累加
  53.                 if(sum1>result || j<=k)
  54.                 {
  55.                     path[k--]=j+1;
  56.                     sum1=d[j]; //舍去后面的 继续累加
  57.                 }
  58.             }
  59.             for(int j=1,k=1;j<=b;j++)
  60.             {
  61.                 if(j>1) System.out.print(" ");
  62.                 if(k<=c-1 && path[k]==j)
  63.                 {
  64.                     System.out.print("/");
  65.                     k++;
  66.                 }
  67.                 System.out.print(d[j]);
  68.             }
  69.         }
  70.     }
  71. }

java代码和C++代码 实际上是一样的 但是poj系统是jdk 1.5 我在自己的idea上运行测试代码可以通过样例
但是poj系统不行

换成C++ 就可以啦~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include<algorithm>

using namespace std;
const int N = 510;
const int INF = 0x7fffffff;
int dp[N][N]; // 方程 : dp[i][j] = min(dp[i][j], max(dp[i-1][v], sum[j]-sum[v])) i 个人 抄写 前j 本书
int sum[N];
int a[N];
int path[N];

int main() {
    int T, m, k, i, j, v;// tmp;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &m, &k);
        for (i = 0; i <= k; i++) {
            for (j = 0; j <= m; j++) {
                dp[i][j] = INF;
            }
        }
        memset(sum, 0, sizeof(sum));
        for (i = 1; i <= m; i++) { /// 书的页数
            scanf("%d", &a[i]); //a[1] 到 a[9]初始化为书的页数
            sum[i] += (sum[i - 1] + a[i]); //sum[i]存储啊a[1]到a[i]的累加和
            dp[1][i] = sum[i];  //也就是一个人抄写i本书的时间
        }
        for (i = 2; i <= k; i++) {
            for (j = i; j <= m; j++) { //i个人抄写j本书 j要大于等于i
                for (v = i - 1; v <j; v++) { //v=1时候 就是前i-1个人抄写1本书
                    //v=2的时候 就是前i-1个人抄写两本书
                    //因为每个人至少要抄一本书 所以前i-1个人至少要抄i-1本书 也就是v=i-1
                    {   

                        if (dp[i][j] > max(dp[i - 1][v], sum[j] - sum[v]))
                            dp[i][j] = max(dp[i - 1][v], sum[j] - sum[v]);
                    }
                }
            }
        }
        int ans = dp[k][m]; //最少时间数
        int t_sum = 0;
        for (i = m, j = k - 1; i >= 1; i--) {   //k个人必有k-1个分割点
            t_sum += a[i]; //从后向前的累加和
            if (t_sum > ans || i <= j) { //如果累加和大于最少时间数 则为分割点
                path[j--] = i + 1; // 3 4 5
                t_sum = a[i]; //从分割点之前继续累加
            }
        }
        for (i = j = 1; i <= m; i++) {
            if (i > 1) printf(" ");
            if (j < k && path[j] == i) { //遍历path数组 得到结果
                printf("/ ");
                j++;
            }
            printf("%d", a[i]);
        }
        printf("\n");
    }
    system("pause");
    return 0;
}