首页 > 试题广场 >

小美和大富翁

[编程题]小美和大富翁

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

$\,\,\,\,\,\,\,\,\,\,$ 小美在玩《大富翁》游戏，游戏中有 $n+1$ 个城市排成一排，编号从 $0$ 到 $n$ ，第 $i$ 个城市上有一个数字 $a_i$ ，表示到达第 $i$ 个城市可以获得 $a_i$ 枚金币。
$\,\,\,\,\,\,\,\,\,\,$ 每一轮开始时小美会获得四张卡牌，分别可以跳跃 1、2、3、4 个城市，例如小美可以从城市1跳跃 $3$ 个城市到达城市4。当小美使用完这 4 张卡牌后，会开启新的一轮。
$\,\,\,\,\,\,\,\,\,\,$ 初始时，小美拥有 $0$ 枚金币，在任意时刻，小美的金币数量都必须大于等于 $0$ ，小美想知道她从第 $0$ 个城市出发，到达第 $n$ 个城市最多可以获得多少枚金币。

输入描述:

第一行输入一个整数  表示城市个数。
第二行输入  个整数  表示到达城市1到n可以获得的金币数量（第0个城市无法获得金币）。

输出描述:

在一行上输出一个整数表示答案；如果无法到达第  个城市，则输出  。

示例1

输入

10
-1 2 3 4 -9 -9 -1 3 -1 -1

输出

说明

最优的方法是：
第 1 步：使用跳跃 3 的卡牌，从 0 跳到 3 ，获得 3 枚金币；
第 2 步：使用跳跃 1 的卡牌，从 3 跳到 4 ，获得 4 枚金币，共有 7 枚金币；
第 3 步：使用跳跃 4 的卡牌，从 4 跳到 8 ，获得 3 枚金币，共有 10 枚金币；
第 4 步：使用跳跃 2 的卡牌，从 8 跳到 10 ，获得 -1 枚金币，共有 9 枚金币。

算法知识视频讲解

Mag1c0nch

发表于 2024-11-28 23:27:12

四张牌每次用一张考虑状压dp[1111][i] 代表人在第 i 位且四张牌都有的情况下的最优答案dp[1010][i] 代表人在第 i 位只有4，2号牌的情况下的最优答案不难发现在任意位置，能转移而来的情况只有最大 15 种，我们可以直接遍历所有情况，然后判断是否存在一个合法的历史情况，如果存在，那展开全文