当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2980:Do it!

题目描述

You are the boss of a small lighting fixture company which has n employees. Inspired by Ben Stiller’s character in Starsky and Hutch, you have recently taken on the habit of telling your employees to “do it!” when you want things done. While n+ of the n employees respond positively to your “do it!”s, n employees respond negatively and n0 are neutral to your words.

At time 0, each of your employees begins working alone on building a lighting fixture. Each lighting fixture takes 100 units of labor to finish. Normally, each of your employees contributes r units of labor towards finishing his/her lighting fixture during each time interval (or the amount of labor units remaining for the fixture, whichever is smaller). Thus, an employee would normally take ceiling(100 ⁄ r) time intervals to finish his or her lighting fixture. During an interval, however, if you yell “do it!” over the company intercom, employees who respond positively to your command will do r + 2 units of labor during that time interval, whereas employees who respond negatively will do r − 1 units of labor during the time interval.

Assuming that each employee works on only his or her lighting fixture, and assuming that you yell “do it!” at most once during each time interval, your goal is to plan a sequence of “do it!”s so as to ensure that the sum of the times needed to finish all n lighting fixtures is minimized.

输入解释

The input test file will contain multiple test cases. Each input test case will be given as a line containing four integers, n+, n, n0, and r (where 0 ≤ n+, n, n0 ≤ 1000 and 1 ≤ r ≤ 100). The end-of-file is marked by a test case with n+ = n = n0 = r = 0 and should not be processed.

输出解释

For each input case, the program should print the minimum sum of times needed to finish all n lighting fixtures.

输入样例
3 1 1 2
1 3 0 2
0 0 0 0
输出样例
188
200
提示

In first test case, one optimal strategy is to yell “do it” in each of the first 25 time intervals. As a result, the 3 positively-responding employees provide 4 units of labor per time interval and thus finish their fixtures in 25 time units. The 1 negatively-responding employee will provide 1 unit of labor per time interval for the first 25 time intervals, 2 units of labor per time interval afterwards, and thus will finish in 25 + 38 = 63 time units. Finally, the neutral employee will always provide 2 units of labor per time interval and hence will finish in 50 time units. This gives a total of 3(25) + 63 + 50 = 188 time units.

In the second test case, an optimal strategy is to never yell “do it”. Thus all four employees finish in 50 time units so the total amount of time taken is 200 time units.


该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Stanford Local 2005

源链接: POJ-2980

最后修改于 2020-10-29T06:49:02+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536