解题报告
题目来源：
PKU 1505 Copying Books
算法分类：
DP
原文：
Copying Books
|
Time Limit: 3000MS
|
|
Memory Limit: 10000K
|
|
Total Submissions: 1806
|
|
Accepted: 404
|
Description
Before the
invention of book-printing, it was very hard to make a copy of a book. All the
contents had to be re-written by hand by so called scribers. The scriber had
been given a book and after several months he finished its copy. One of the
most famous scribers lived in the 15th century and his name was Xaverius
Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying
and boring. And the only way to speed it up was to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous
Antique Tragedies. The scripts of these plays were divided into many books and
actors needed more copies of them, of course. So they hired many scribers to
make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that
may have different number of pages (p1, p2 ... pm) and you want to make one
copy of each of them. Your task is to divide these books among k scribes, k
<= m. Each book can be assigned to a single scriber only, and every scriber
must get a continuous sequence of books. That means, there exists an increasing
succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk
= m such that i-th scriber gets a sequence of books with numbers between bi-1+1
and bi. The time needed to make a copy of all the books is determined by the
scriber who was assigned the most work. Therefore, our goal is to minimize the
maximum number of pages assigned to a single scriber. Your task is to find the
optimal assignment.
Input
The input
consists of N cases. The first line of the input contains only positive integer
N. Then follow the cases. Each case consists of exactly two lines. At the first
line, there are two integers m and k, 1 <= k <= m <= 500. At the
second line, there are integers p1, p2, ... pm separated by spaces. All these
values are positive and less than 10000000.
Output
For each
case, print exactly one line. The line must contain the input succession p1,
p2, ... pm divided into exactly k parts such that the maximum sum of a single
part should be as small as possible. Use the slash character ('/') to separate
the parts. There must be exactly one space character between any two successive
numbers and between the number and the slash.
If there is more than one solution, print the one that minimizes the work
assigned to the first scriber, then to the second scriber etc. But each scriber
must be assigned at least one book.
Sample Input
2
9
3
100
200 300 400 500 600 700 800 900
5
4
100
100 100 100 100
Sample Output
100
200 300 400 500 / 600 700 / 800 900
100
/ 100 / 100 / 100 100
Source
Central Europe 1998
中文描述：
题目大意是给你m（1…m）本书，每本书有Pm页，用k（k<=m）个员工来复印这些书。每本书只能分配给一个员工来复印，并且每个员工必须复印一段连续的书籍，每个员工复印的时间取决于所复印书籍的总页数。让你给出相应的分配，使得分配给员工的书籍页数的最大值尽量小。注意，如果有多种分配的方案，使得第一个员工的书籍页数尽量少，其次是第二个、第三个……以此类推。
题目分析：
我们可以从后往前推，最后一个员工，也就是第k个员工，他至少要复印第m本书，至多可以复印第k本到第m本（因为至少要分配给前k-1个员工每人一本书）。假设，第k名员工复制第i（k<=i<=m）本书到第m本书，那么，所有员工复印书籍的最小时间就为第k名员工所需的时间以及前k-1名员工复制前i-1本书所需最小时间的较大的那个时间。这样，问题的规模就从k个员工复印m本书减小到了k-1个员工复印i-1本书，而且求解过程中会不断遇到前a个员工复印前b本书的最小时间。为了减小问题的规模以及记录重复子问题的解，就可以用DP。
但仅仅算出最小时间的不够的，还要给出分配的方案，这个稍微有点繁琐。因为题目中说，如果有多种最优的分配方案，应该让前面的员工分配的页数尽量少。那么，可以从后推，在当前的员工所复印的书籍页数没有超过最大页数的情况下，让其复印的页数最大化。如果超过了最大页数，就把这本书分配给前一名员工。最后再按顺序将分配结果输出出来。
代码：
#include
<cstdio>
#include
<climits>
#include
<cstring>
const int
MAX = 505;
int
book[MAX];
__int64
total[MAX]; //1~n本书的页数
int k, m;
__int64
f[MAX][MAX]; //f[i][j] = k 表示前i个人复制前j本书所需最少时间是k
__int64
max;
void Input
()
{
scanf("%d%d", &m,
&k);
int i;
for (i=1; i<=m; i++)
scanf("%d",
&book[i]);
}
__int64 Sum
(int s, int e) //第s本书到第e本书的总页数
{
return (total[e] - total[s-1]);
}
__int64 Max
(__int64 a, __int64 b)
{
return ( a>b?a:b );
}
__int64 Min
(int x, int y) //前x个人复制前y本书所需的最少时间 x<=y
{
//考虑特殊情况
if ( f[x][y] != -1 )
return f[x][y];
if ( y == 0 )
return ( f[x][y]
= 0 );
if ( x == 0 )
return ( f[x][y]
= INT_MAX );
int i;
__int64 temp;
f[x][y] = INT_MAX;
for (i=x-1; i<y; i++)
{
//第x个人复制第i+1到第y本书与前x-1个人复制前i本书的时间较大的时间
temp = Max(
Min(x-1, i), Sum(i+1, y) );
if ( temp <
f[x][y] )
{
f[x][y]
= temp;
}
}
return f[x][y];
}
void Output
()
{
int i, p;
__int64 temp;
int slash[MAX];
max = f[k][m];
memset(slash, 0, sizeof(slash));
temp = 0;
p = k;
for (i=m; i>0; i--)
{
//让后面的员工尽量复印最多的书籍
if ( temp +
book[i] > max || i < p )
{
slash[i]
= 1;
temp
= book[i];
p
--;
}
else
{
temp
+= book[i];
}
}
for (i=1; i<=m; i++)
{
printf("%d",
book[i]);
if ( slash[i] ==
1 )
printf("
/ ");
else if ( i != m
)
printf("
");
}
printf("\n");
}
void Solve
()
{
int i, j;
//预处理书籍页数的和
total[0] = 0;
for (i=1; i<=m; i++)
total[i] =
total[i-1] + book[i];
memset(f, -1, sizeof(f));
Min(k, m);
Output();
}
int main ()
{
int test;
scanf("%d",
&test);
while ( test-- )
{
Input ();
Solve ();
}
return 0;
}
程序分析与心得：
时间复杂度O(n2)，空间复杂度O(n2)。
在用记忆化搜索解决DP问题时，往往比较符合人的思维，容易想到模型，编程比较简单。在解题过程中，除了可以按照常理顺着推，也可以尝试逆向思维，从最后的状态倒着推，这样可以使问题想得更加透彻，有比较好的效果。