大富翁游戏规则如下
-
玩家起始会获得一定资本M金币
-
玩家每一次可以走一个格,或者跳两个格;走一格耗费2个金币能量;跳两个格,耗费3个金币能量;金币只有满足能量消耗时,才能继续往下走
-
玩家每走到一个格,会得到这个格的奖励,每个格的奖励金币数为非负整数
-
当玩家走到这个格后,总金币数不足以支持下一步金币消耗时,则不能继续往下走,游戏结束
- 玩家第一步可以选择走一步进第1格或者跳2步进第2格起始,玩家可以选择在任意一格结束游戏
大富翁游戏规则如下
玩家起始会获得一定资本M金币
玩家每一次可以走一个格,或者跳两个格;走一格耗费2个金币能量;跳两个格,耗费3个金币能量;金币只有满足能量消耗时,才能继续往下走
玩家每走到一个格,会得到这个格的奖励,每个格的奖励金币数为非负整数
当玩家走到这个格后,总金币数不足以支持下一步金币消耗时,则不能继续往下走,游戏结束
共两行
第一行为一个整数,表示玩家的起始资本M第二行为一个整数数组,由空格分割,表示一个顺序奖励方格,数组中的值表示方格中的奖励
仅一行一个整数表示答案,即玩家能获得的最多的金币数量
3 1 3 1 2 4
4
3 1 3 2 3 1 1 1 5 10
4
def test4(): M = int(input()) # 货架长度,每一层最多摆两个商品 golds = list(map(int,input().split())) # 商品长度 step_costs = [2,3] n = len(golds) dp = [0] * (n+1) dp[0] = M gold = 0 # print("--") for i in range(1,n+1): for j,cur_cost in enumerate(step_costs): if i -j-1 <0: continue # 当前位置的收益不能撑起此次跳跃 if dp[i-j-1] < cur_cost: continue # print(i,j,dp[i],dp[i-j-1]) dp[i] = max(dp[i],dp[i-j-1] + golds[i-1] - cur_cost) # print("i: {}, j: {}, prev: {}, now: {}".format(i,j,dp[i-j-1],dp[i])) gold = max(gold,dp[i]) # 保留历史的最大收益 # print(dp) gein = max(dp[1:]) # print(gold) print(gein) if __name__ == "__main__": test4()