问题:
Bob计划在一组n天内工作,在每一天i上都有一个任务;每个任务持续一天,必须在给定的第i天完成,Bob将获得xi美元报酬。Bob不能连续工作超过5个任务,在每5天至少需要休息一天。
已知数字x1...xn,哪些天应该让Bob执行任务,哪些天应该让他休息,以便尽可能赚取更多的钱而不超过5天工作?你的解决方案应该是O(n)。
我的问题:
我在想这个问题的递归公式时遇到了麻烦。我已经思考了很长时间,最初的想法是让p[i]=max{x_i + x_i-1 + ....+ x_i-4},其中p[i]是从第i-4天到第i天可获得的最大利润。但是我意识到,首先,这并没有考虑到最优解可能有两个连续的工作日,其次,我没有建立在之前的解决方案之上。
我的问题是:有人能够帮我理解这个问题的结构吗?我觉得我只是没有理解会使解决方案容易看到的关键属性。
提前感谢!
Bob计划在一组n天内工作,在每一天i上都有一个任务;每个任务持续一天,必须在给定的第i天完成,Bob将获得xi美元报酬。Bob不能连续工作超过5个任务,在每5天至少需要休息一天。
已知数字x1...xn,哪些天应该让Bob执行任务,哪些天应该让他休息,以便尽可能赚取更多的钱而不超过5天工作?你的解决方案应该是O(n)。
我的问题:
我在想这个问题的递归公式时遇到了麻烦。我已经思考了很长时间,最初的想法是让p[i]=max{x_i + x_i-1 + ....+ x_i-4},其中p[i]是从第i-4天到第i天可获得的最大利润。但是我意识到,首先,这并没有考虑到最优解可能有两个连续的工作日,其次,我没有建立在之前的解决方案之上。
我的问题是:有人能够帮我理解这个问题的结构吗?我觉得我只是没有理解会使解决方案容易看到的关键属性。
提前感谢!