首页 > 试题广场 >

小歪和大富翁2.0

[编程题]小歪和大富翁2.0
  • 热度指数：376 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小歪在玩《大富翁》游戏，游戏中 n 个城市围成一圈，编号从 0 到 n-1 ，即第 n-1 个城市的下一个城市是第 0 个城市。第 i 个城市上有一个数字 a_i ，表示第一次到达第 i 个城市可以获得 a_i 枚金币。
\,\,\,\,\,\,\,\,\,\,每一轮开始时小歪会获得 4 张卡牌，分别可以跳跃 1、2、3、4 个城市，例如小歪可以从城市一跳跃 3 个城市到达城市四。当小歪使用完这 4 张卡牌后，会开启新的一轮。
\,\,\,\,\,\,\,\,\,\,初始时，小歪拥有 0 枚金币，小歪想知道她从第零个城市出发（出发时不会获得金币），经过 k 轮后最多可以获得多少枚金币。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n 和 k\ (10 \leq n \leq 10^5;\ 1 \leq k \leq 10^9) 代表城市个数、游戏轮数，数据保证 n 一定是 10 的倍数。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\ (-10^9 \leq a_i \leq 10^9) 表示第一次到达城市 0 到 n-1 可以获得的金币数量。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表小歪能获得的最多金币数量。
示例1

输入

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

输出

9

说明

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

输入

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

输出

10

说明

\,\,\,\,\,\,\,\,\,\,最优的方法是：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 1 步：使用跳跃 3 的卡牌，从 0 跳到 3 ，获得 3 枚金币；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 2 步：使用跳跃 1 的卡牌，从 3 跳到 4 ，获得 4 枚金币，共有 7 枚金币；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 3 步：使用跳跃 4 的卡牌，从 4 跳到 8 ，获得 3 枚金币，共有 10 枚金币；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 4 步：使用跳跃 2 的卡牌，从 8 跳到 0 ，获得 -1 枚金币，共有 9 枚金币。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 5 步：使用跳跃 2 的卡牌，从 0 跳到 2 ，获得 2 枚金币，共有 11 枚金币；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 6 步：使用跳跃 1 的卡牌，从 2 跳到 3 ，获得 0 枚金币（不是第一次到达），共有 11 枚金币；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 7 步：使用跳跃 4 的卡牌，从 3 跳到 7 ，获得 -1 枚金币，共有 10 枚金币；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 8 步：使用跳跃 3 的卡牌，从 7 跳到 0 ，获得 0 枚金币（不是第一次到达），共有 10 枚金币。
算法知识视频讲解
开通博客

暂无题解

问题信息

动态规划 位运算 组合数学 阿里云
难度：
1条回答 599浏览

热门推荐

相关试题

小歪和大富翁2.0

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号