刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

编程实现:

小明去游乐场玩飞镖扎气球的游戏,一共有n个气球,依次排成一行,每个气球上有一个数字,表示这个气球的分值。

游戏计分规则:

1、戳破1个气球,将获得其本身及左右相邻气球,共三个分值相乘的分数;

2、如果戳破的气球左边或右边没有气球,则获得其本身及相邻气球,共两个分值相乘的分数;如果被戳破的气球左边和右边都没有气球(是最后一个被戳破的气球),则这个气球本身的分值作为分数。

3、已经被戳破的气球不再计算。

飞镖数量不限,可以任意选择顺序戳破气球,根据计分规则,争取使得游戏最后得分最高。

例如:一共有3个气球,分值分别为2,4,6。

若想获得最高得分:

1)先戳破4,得分为2X4X6=48;

2)再戳破2,得分为2X6=12,累计得分60;

3)再戳破6,得分为6,累计得分66;

最后总得分为66,为最高得分。

输入描述:

输入n个正整数,表示气球的分值,且正整数之间以一个英文逗号隔开

输出描述:

输出正整数,表示戳破所有气球后获得的最高分数


样例输入:

2,4,6

样例输出:

66

使用微信搜索喵呜刷题,轻松应对考试!

答案:

br />```pythondef max_score(scores):n = len(scores)dp = [[0] * n for _ in range(n)]for i in range(n):dp[i][i] = scores[i]for length in range(2, n + 1):for i in range(n - length + 1):j = i + length - 1dp[i][j] = max(dp[i][j], dp[i+1][j] * scores[i], dp[i][j-1] * scores[j])for k in range(i+1, j):dp[i][j] = max(dp[i][j], dp[i][k] * dp[k+1][j] * scores[k])return dp[0][n-1]scores = list(map(int, input().split(',')))print(max_score(scores))```

解析:

【喵呜刷题小喵解析】

本题可以使用动态规划来解决。

首先,我们定义一个二维数组dp,其中dp[i][j]表示戳破第i个到第j个气球所能获得的最大分数。

然后,我们初始化dp数组,将dp[i][i]设为第i个气球的分值,表示戳破一个气球的情况。

接着,我们使用两层循环,外层循环表示戳破气球的数量,内层循环表示戳破的气球的位置。

在内层循环中,我们计算戳破第i个到第j个气球所能获得的最大分数。

首先,我们计算戳破第i+1个到第j个气球所能获得的最大分数,再乘以第i个气球的分值,得到戳破第i个气球的情况。

其次,我们计算戳破第i个到第j-1个气球所能获得的最大分数,再乘以第j个气球的分值,得到戳破第j个气球的情况。

最后,我们遍历第i+1个到第j-1个气球,计算戳破第i个到第k个气球所能获得的最大分数,再乘以戳破第k+1个到第j个气球所能获得的最大分数,再乘以第k个气球的分值,得到戳破第k个气球的情况。

最后,我们返回dp[0][n-1],表示戳破所有气球所能获得的最大分数。

注意,在输入时,我们需要将输入的字符串转换为整数列表。

在输出时,我们直接输出戳破所有气球所能获得的最大分数。
创作类型:
原创

本文链接:编程实现: 小明去游乐场玩飞镖扎气球的游戏,一共有n个气球,依次排成一行,每个气球上有一个数字,表示

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share