http://acm.zju.edu.cn/show_problem.php?pid=1012
ACM的题，我知道要用枚举法，但是做起来又很困难，怎么样才能举遍所有情况呢？
请指教，不高兴写程序，说说具体算法，谢了！

[此贴子已经被作者于2006-7-13 21:25:04编辑过]

Mr.Ronald 是负责管理ACM（代理计算数学问题)主机的人员。他负责管理主机机精确计算其他公司交付的

工作（程序），然后得出工作完成后应该得到的报酬。所以主机的资源对ACM来说很珍贵。Mr.Ronald需要

编排一个顺序让这些工作在主机上运行。如果某一个工作想要进入主机计算，他必须检查主机所闲置的资

源，如果闲置的资源多于此工作所需求的资源，那么他要分配主机的资源给这些工作（可能原本就有工作

在运行），否则，那么这个工作会被挂起知道主机资源足够为止。

因为对这个任务的不熟悉，Mr.Ronald推敲了任务的所有细节，渐渐地，他开始能够胜任这个任务了。此

外，他总结出了以下规则：
1.主机有M的CPUs和N的内存可以被分派利用。

2.有若干个工作组成的队列在等待着被执行。你可以假设队列足够大来容纳所有等待操作的工作。

3.一件工作Ji（i为角标，下同）需要Ai的CPUs和Bi的内存，进入队列的时间为Ti。工作必须在Ui前完成

。等到所有工作成功完成后，ACM 会的出报酬Vi($)。如果工作在规定时间内完成，超前完成的没小时将

获得Wi($)的奖励。如果工作晚完成了，将会罚金Xi($)每小时。举个例子，我们假设完成一个工作的报酬

为10$，规定时刻为8，罚金是超时每小时2$，如果这个工作在时刻10完成，那么ACM会得出的报酬为10-

(10-8)*2=6$.

4.如果某项工作开始，那么它所需求的CPU和内存的资源就被这项任务占用，不能够在分派给其他的任务

同时进行处理。等到这件工作完成以后，这些被占用的资源会被释放。如果主机的资源足够，可以同时运

行更多的工作。

5.为了共享主机的运算能力，每个工作将在1小时内完成。你可以认为每件工作需要一个小时来完成。

6.如果没有任何工作正在进行处理，那么主机将闲置直到有工作加入。

7.如果有多于一个的任务加入到队列中，报酬高的工作将被先运行，你可以假设每个工作的报酬都是不同

的(Vi≠Vj)。

8.如果闲置的CPU和内存不能够满足任务的所需求的数量，那么这个任务将被挂起一小时且不占用任何资

源。一小时后，将会再次检查主机的闲置资源是否能够满足这项工作，不管其他正在处理的工作的情况。

9.如果有多个任务被挂起，那么先到达的任务会被最先重新分配。

通过这些总结，Mr.Ronald可以把他的日常工作处理的非常出色。不过现在，除了日常工作，ACM还要求他

凭借任务清单估算出收入。给出时刻F，为所有任务完成的时间限制。例如，某项工作Ji，如果Ui>F，那

么这项工作不会被执行，且不能规入账目进行计算报酬。但是那些Ui<=F被执行的工作需要计算报酬。如

果工作没有被执行，那么它不会带来任何ACM的收入，也就是说，只有超时的部分的罚金需要被计算。

确实，Mr.Ronald的统筹能力不那么足够，而且他不喜欢手工估算。所以他觉得完成任务不容易。你能够

帮助他解决这个问题吗？

输入：
输入将包含若干组数据，每组将会提供主机资源和工作清单等信息。每组数据第一行是一个整数F，0 <=

F <= 10000,这是时间限制（工作必须在这个时间能完成，才能被计算报酬）。第二行是三个整数M,N,L

(M, N, L >= 0)。M是主机CPU的大小，N为内存的大小。L表示有任务清单中任务的数量，最大值为1000。

后面L行描述这组数据所有工作的信息。每行，工作Ji的资料由Ai, Bi, Ti, Ui, Vi, Wi, Xi. Ai ，Bi这

7个整数组成，分别指出CPU和内存的需求(Ai, Bi >= 0)。 Ti 和 Ui分别指任务到达的时刻，和规定完成

的时刻。(0 <= Ti <= Ui). Vi, Wi, Xi ，分别是基本报酬，每小时的奖励和惩罚值(Vi, Wi, Xi >= 0)

。

输入将以一个数据为空的组结束，即(F＝0).这组数据不用处理。

输出：
你的程序必须凭借工作清单估算出总收入。每个数据组，打印出组的序号，接一个冒号，一个空格，然后

才是收入。

打印一个空行在每组输出数据之间。

提示：别计算没有执行的工作，他们的时间线晚于限制时间F。

输入的列子：
10
4 256 3
1 16 2 3 10 5 6
2 128 2 4 30 10 5
2 128 2 4 20 10 5
0

输出的例子：
Case 1: 74

题目来源：亚洲赛区，上海（中国大陆）

[此贴子已经被作者于2006-7-13 21:41:41编辑过]

唉，我翻译成中文了还是没理解题意，我解释下例子怎么算的吧。
输入的列子：
10
4 256 3
1 16 2 3 10 5 6
2 128 2 4 30 10 5
2 128 2 4 20 10 5
0

输出的例子：
Case 1: 74

三项工作2时刻同时到达，第二第三项工作2时刻一起进入主机，第一项挂起，在3时刻完成工作后，比预定时间时刻4，快了一小时，那么报酬分别为30+10×（4-3）＝40，20＋10×（4-3）＝30，那么第一项工作在3时刻进入主机，完成工作后是时刻4，晚了一小时，那么报酬为10＋（3－4）×6＝4，将三项报酬加起来得74。你可以试试其他的算法，比如一项一项完成，得到的报酬都没有74大，所以这是最优解。

所以，没什么规律可言，唯一的办法就是用枚举法，把每种情况都列举出来，算出其报酬，然后再把最大的挑出来。
当然了，三项任务真要写也不难，因为最多有四种情况，要么一项一项做，要么先一项后两项，要么先两项后一项，再就是三项一起（当然啦，资源够不够要判断过）。但是你看看题目，任务最大数是1000项，任务一多，比如有7项，这就意味着有可能先两项后三项再两项。。。也可以先两项后一项再四项，大家想想如果要把所有的情况举遍是否很复杂？

再退一步，如果我知道任务有几项，那还是写的出来的，繁是繁了点，但是有几项任务是用户输入的啊，是不知道的，要写在一个程序里面是否就非常困难。

当然，我迄今想到可以减少计算的办法是先判断资源最大能够进行几项任务，再枚举，但是依然是老问题，得出的结果依然是不知道的，那么问题就跟上面一样了，怎么算才能涵盖所有呢？
这就是问题关键了，说通俗点就是不知道怎么循环，更加不知道怎么控制循环结束，也就是我要问的地方。

[此贴子已经被作者于2006-7-13 21:27:56编辑过]

........
没单位的啊～你就当M个，N兆好了！

楼上的再说清楚些好吗？
怎么才能按要求模拟呢？

绝望顶起

我才晕，这么好算我干吗要问啊？
你要想可以同时进行两项三项甚至n项（只要资源许可）工作的啊，这样才能产生最大的报酬。单纯的排序是没用的.
而且随着任务的增多，更加复杂。

唉，我翻译成中文了还是没理解题意，我解释下例子怎么算的吧。
输入的列子：
10
4 256 3
1 16 2 3 10 5 6
2 128 2 4 30 10 5
2 128 2 4 20 10 5
0

输出的例子：
Case 1: 74

三项工作2时刻同时到达，第二第三项工作2时刻一起进入主机，第一项挂起，在3时刻完成工作后，比预定时间时刻4，快了一小时，那么报酬分别为30+10×（4-3）＝40，20＋10×（4-3）＝30，那么第一项工作在3时刻进入主机，完成工作后是时刻4，晚了一小时，那么报酬为10＋（3－4）×6＝4，将三项报酬加起来得74。你可以试试其他的算法，比如一项一项完成，得到的报酬都没有74大，所以这是最优解。

所以，没什么规律可言，唯一的办法就是用枚举法，把每种情况都列举出来，算出其报酬，然后再把最大的挑出来。
当然了，三项任务真要写也不难，因为最多有四种情况，要么一项一项做，要么先一项后两项，要么先两项后一项，再就是三项一起（当然啦，资源够不够要判断过）。但是你看看题目，任务最大数是1000项，任务一多，比如有7项，这就意味着有可能先两项后三项再两项。。。也可以先两项后一项再四项，大家想想如果要把所有的情况举遍是否很复杂？

再退一步，如果我知道任务有几项，那还是写的出来的，繁是繁了点，但是有几项任务是用户输入的啊，是不知道的，要写在一个程序里面是否就非常困难。

当然，我迄今想到可以减少计算的办法是先判断资源最大能够进行几项任务，再枚举，但是依然是老问题，得出的结果依然是不知道的，那么问题就跟上面一样了，怎么算才能涵盖所有呢？
这就是问题关键了，说通俗点就是不知道怎么循环，更加不知道怎么控制循环结束，也就是我要问的地方。

[此贴子已经被作者于2006-7-13 21:36:14编辑过]