Algorithm 版 (精华区)

发信人: GREnTOFEL (Crazy Plucking), 信区: Algorithm
标  题: 动态规划----复制书稿(转载)
发信站: 哈工大紫丁香 (2002年07月06日21:52:30 星期六), 站内信件

【 以下文字转载自 Programming 讨论区 】
【 原文由 zjliu 所发表 】
发信人: violinist (巷战狙击手), 信区: Algorithm
标  题: 动态规划----复制书稿
发信站: 日月光华 (Fri Jul  5 08:33:23 2002)

〖题目描述〗
假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P

1，P2，…PM）。任务是将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写

员进行复制，而每个抄写员所分配到的书必须是连续顺序的。
意思是说，存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m，这样，第

I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的，并且每个抄写

员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那

个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽

可能小（如存在多个最优方案，只输出其中一种）。
(GDOI''99 Books).

〖输入格式〗
第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.


〖输出格式〗
共k行。每行两个整数：第I行表示第I抄写员抄的书本编号起止。

〖输入输出样例〗
输入样例 输出样例
9 3
1 2 3 4 5 6 7 8 9  1 5
6 7
8 9


--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.154]