我要招人

去企业版

首页 > 试题广场 >

大富翁游戏

[编程题]大富翁游戏

热度指数：1233 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

大富翁游戏规则如下

玩家起始会获得一定资本M金币
玩家每一次可以走一个格，或者跳两个格；走一格耗费2个金币能量；跳两个格，耗费3个金币能量；金币只有满足能量消耗时，才能继续往下走
玩家每走到一个格，会得到这个格的奖励，每个格的奖励金币数为非负整数
当玩家走到这个格后，总金币数不足以支持下一步金币消耗时，则不能继续往下走，游戏结束
玩家第一步可以选择走一步进第1格或者跳2步进第2格起始，玩家可以选择在任意一格结束游戏

问玩家游戏中，最多能得到多少个金币？

输入描述:

共两行

第一行为一个整数，表示玩家的起始资本M

第二行为一个整数数组，由空格分割，表示一个顺序奖励方格，数组中的值表示方格中的奖励

输出描述:

仅一行一个整数表示答案，即玩家能获得的最多的金币数量

示例1

输入

3
1 3 1 2 4

输出

示例2

输入

3
1 3 2 3 1 1 1 5 10

输出

算法知识视频讲解

pein531

直接用动态规划进行求解，每次比较走一格和跳两格哪一种收益更大

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)

发表于 2021-01-20 22:59:06 回复(2)

想去--打螺丝

这题必须要踩上了格子才能返回，我把初始资金也加入ret的判断就不行了，只能过37。所以第一步是必须要走的，无法逃避

发表于 2022-08-13 18:34:56 回复(0)

人海追风

真滴费劲

#include<iostream>

#include<vector>
using namespace std;

int main()
{
int sum;
cin>>sum;
vector<int> nums;
int cur ;
while(cin>>cur)
{
nums.push_back(cur);
}
int ret= 0;
vector<int> dp(nums.size()+1, 0);
dp[0]=sum;
for(int i=1;i<=nums.size();i++)
{
if(i-1>=0&&dp[i-1]>=2) {dp[i] = max(dp[i], dp[i-1]-2+nums[i-1]);} //nums的下标比dp的下标小1
if(i-2>=0&&dp[i-2]>=3) {dp[i] = max(dp[i], dp[i-2]-3+nums[i-1]);}
ret = max(ret, dp[i]);
}
cout<<ret;
return 0;
}

编辑于 2021-01-06 10:53:58 回复(0)

牛客634241998号

import java.util.Scanner;

#思路：动态规划，dp[i]表示到达索引为i的元素时的最大金币数，到达i可能是从i-1来的也可能是从i-2来的，分别计算从哪个来时金币数量大。

初始化：dp[0]=m-2+nums[0]

dp[1]=max(省略了)

public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
scanner.nextLine();
String[] nums = scanner.nextLine().split(" ");
solve(m,nums);
}

private static void solve(int m, String[] nums) {
if(m<2){
System.out.println(m);
return;
}

int[] dp = new int[nums.length];//dp[i]表示到达下标为i的节点时具有的金币数量
dp[0] = m-2+Integer.valueOf(nums[0]);
dp[1] = m<3?dp[0]-2+Integer.valueOf(nums[1]): Math.max(dp[0]-2+Integer.valueOf(nums[1]),m-3+Integer.valueOf(nums[1]));
int max= Math.max(dp[0],dp[1]);
for(int i=2;i<nums.length;i++){
//到达i即有可能时从i-2来的也有可能时从i-2来的
//计算从i-1来的现金奖励
int pre = dp[i-1]>=2?dp[i-1]-2+Integer.valueOf(nums[i]):0;
int prePre = dp[i-2]>=3?dp[i-2]-3+Integer.valueOf(nums[i]):0;
dp[i] = Math.max(pre,prePre);
if(dp[i]==0){
//说明无论怎样根本到达不了这里
break;
}
max = dp[i]>max?dp[i]:max;
}
System.out.println(max);
}
}

发表于 2022-09-17 22:45:47 回复(0)

菲尼克斯弗兰克

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);
    }
}

发表于 2022-08-28 22:11:43 回复(0)

Python

whreris

感谢前面的老哥，迭代的时候是要加上起跳的格子的收益

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()

发表于 2021-08-20 20:36:26 回复(0)