我在Google Code Jam中阅读optimisation problem about energy。 (现在比赛结束了,所以可以谈谈)如何解决“管理你的能量”?
今天你有一个非常繁忙的日历,充满了重要的事情要做。 您努力准备,并确保所有活动不重复 。现在是早上,你担心尽管你的热情很高,但你不会有精力去完成所有这些,并且完全参与 。
你将不得不小心管理你的能量。准确地说,你开始一天的能量 - E焦耳的能量,完整的 。你知道你不能在零焦以下去 ,否则你会因疲惫而下降。您可以在每项活动上花费任何 非负的整数焦耳(如果您觉得懒惰,您可以花费 为零),并且在每次活动之后,您将重新获得能量焦耳R 。然而,无论你多么懒惰,你在任何时候都不能有比能量高出几焦耳的能量;任何额外的能量,你会 重获过去那一点是浪费。
现在,一些事情(如解决Code Jam问题)比其他事情更重要 。对于第i项活动,您有一个值vi,表示 此活动对您而言有多重要。您从每个 活动中获得的收益是活动的价值乘以您在活动上花费的能量(以焦耳为单位)。你想管理你的能量,这样你的总收益将尽可能大。
请注意,您无法重新排列日历中的活动。你只需要 必须管理你的能量以及你可以用你的日历 有。
输入
输入的第一行给出的测试用例的数量,T T检验 例遵循。每个测试用例由两行描述。第一个 包含三个整数:E,能量的最大(和最初)金额,R,您在每次活动后重新获得的金额,以及N,当天计划的活动数量。第二行包含N 整数vi,描述您今天计划的 活动的值。
输出
对于每一个测试的情况下,输出包含一个行“案例#X为:y”,其中x是 的情况下数(从1开始),而y是可以 通过管理实现的最大增益你那天的精力。
这个问题怎么解决?我在想如果它可以通过动态编程来解决。任何线索?
是的!你不需要知道动态编程来解决这个问题,但它是一个明智的攻击线。任何时候做出最佳决定的理由都不取决于以前的决定,除非通过他们留给你的能量。这表明定义'f(n,e)'是n次活动之后的最优分数,给你留下e点能量。所以'f(0,e)= 0'。你可以用'f(n-1,?)'和'v_n'来表示'f(n,·)'的递归关系。原问题的答案是'max_e f(N,e)'。 – 2013-04-28 13:25:08
感谢您编辑问题和重演。 – 2013-05-02 12:13:38