大富翁游戏规则如下
-
玩家起始会获得一定资本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
M = int(input()) reward = list(map(int, input().strip().split())) n = len(reward) dp = [0]*(n + 1) dp[0] = M # 起始的本金(0表示游戏还未开始) # 动态规划求解 gold = 0 for i in range(1, n + 1): if i - 1 >=0 and dp[i - 1] >= 2: # 可以走一格的情况下 dp[i] = max(dp[i], dp[i - 1] + reward[i - 1] - 2) # 通过走一格的方式从i-1到i if i - 2 >= 0 and dp[i - 2] >= 3: # 可以跳一格的情况下 dp[i] = max(dp[i], dp[i - 2] + reward[i - 1] - 3) # 通过跳两格的方式从i-2到i gold = max(gold, dp[i]) print(gold)
import java.util.Scanner; public class Main { // 大富翁游戏-最多获得多少金币 public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); in.nextLine(); String[] s = in.nextLine().split(" "); fun(s, m); } // 线性dp问题 public static void fun(String[] s, int m) { int n = s.length; int[] dp = new int[n+1]; // 走到第i格的最大金币数 dp[0] = m; int max = 0; for (int i = 1; i <= n; i++) { int coin = Integer.parseInt(s[i-1]); int a = dp[i-1] >= 2 ? dp[i-1]-2+coin : 0; int b = i-2 >= 0 && dp[i-2] >= 3 ? dp[i-2]-3+coin : 0; dp[i] = Math.max(a, b); max = Math.max(max, dp[i]); } System.out.println(max); } }
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()