最大值最小化（DP）

题目来源：网易有道2013年校园招聘面试一面试题
题目描述：: 在印刷术发明之前，复制一本书是一个很困难的工作，工作量很大，而且需要大家的积极配合来抄写一本书，团队合作能力很重要。
当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书，编号为1,2,3...m, 每本书有1<=x<=100000页，把这些书分配给k个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，你的任务就是找到一个最佳的分配方案，使得所有书被抄完所用的时间最少。

输入：: 输入可能包含多个测试样例。
第一行仅包含正整数 n，表示测试案例的个数。
对于每个测试案例，每个案例由两行组成，在第一行中，有两个整数m和 k， 1<=k<=m<=500。在第二行中，有m个整数用空格分隔。所有这些值都为正且小于100000。

输出：

对应每个测试案例，
输出一行数字，代表最佳的分配方案全部抄写完毕所需要的时间。

样例输入：

2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100

样例输出：

1700
200

思路：
这道题和平衡负载（2013年百度之星3月23号竞赛题目一） 题目很类似，不过要简单些，状态较少。定义状态dp[x][y]为y个人抄写x本书花费的最短时间。状态转移方程为：
dp[x][y] = min{max{dp[x1][y - 1] , sy}} 其中x1取值为[x - 1, y - 1],sy = m[x1 + 1] + m[x2 + 1] + ...+ m[x],(m[x]为第x本书的页数)
具体代码如下：

 1 #include <stdio.h>
 2 
 3 int m, k, n; //m书的本书，k抄写员的个数
 4 int dp[505][505];
 5 int data[505]; //每本书的页数
 6 
 7 #define max(a, b) (a > b ? a : b)
 8 
 9 #define INF 100000000
10 
11 int main(void)
12 {
13     int i, j, l, jj, sum;
14 
15     scanf("%d", &n);
16     for (i = 0; i < n; i ++)
17     {
18         scanf("%d%d", &m, &k);
19         for (j = 1; j <= m; j ++)
20             scanf("%d", &data[j]);
21         //初始化dp
22         dp[0][1] = 0;
23         for (j = 1; j <= m; j ++)
24             dp[j][1] = dp[j - 1][1] + data[j];
25         for (l = 2; l <= k; l ++)
26             for (j = l; j <= m - (k - l); j ++)
27             {
28                 sum = 0;
29                 dp[j][l] = INF;
30                 for (jj = j; jj >= l; jj --)
31                 {
32                     sum += data[jj];
33                     if (max(dp[jj - 1][l - 1], sum) < dp[j][l])
34                         dp[j][l] = max(dp[jj - 1][l - 1], sum);
35                 }
36             }
37         printf("%d
", dp[m][k]);
38     }
39 }

View Code

最大值最小化（DP）

相关推荐