NOC青少儿编程大赛Python初中组决赛真题【解析】-连连看,,

NOC青少儿编程大赛Python初中组决赛真题【解析】-连连看,,

连连看

编程实现: 现在有一个连连看卡牌游戏。有n张卡牌排列在一起，每张卡牌上有一个分数，只要将相邻两张 卡牌连到一起，就会合成一张新的卡牌，卡牌上的分数为之前两张卡牌的分数之和，你将获得新 卡牌分数的相应积分。经过多次操作后，最后只剩一张卡牌，游戏结束。给定初始每张卡牌的分 数，请问最多能获得多少分?

例如:场上有3张卡牌，分数分别为10分、23分、5分，将10分卡牌与23分卡牌合成，可得到 33分卡牌，再将33分卡牌与5分卡牌合成，可得到38分卡牌，获得总分数为33+38=71分为最多 的分数。

输入描述

第一行输入一个正整数n，表示有n张卡牌(1≤n≤100)。第二行输入n个正整数，表示每张卡牌的初始分数(1≤分数≤100)，正整数之间由空格隔开。

输出描述

输出最多可以获得的分数。

输入样例

3

10 23 5

输出样例

71

解析：这是一个比较典型的贪心算法考题

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。它的核心思想是将寻找最优解的问题分为若干个步骤，每一步都采用贪心原则，选取当前最优解。

那么对应本题，要想输出最多可以获得的积分，那么我们每一次合牌都选择和最大的两个数进行合牌。

例如：2、2、3、1；先合并2、3得到5

新的卡牌：2、5、1；5、2合并得到7；

新的卡牌：7、1；7、1合并得到8；

最后输出：20

参考代码：

#将输入的一串数字分割，存入列表a = list(map(int,input().split()))#卡牌数量（列表长度）length=len(a)max_step=0#每一次合牌积分max_index=0#合并的牌的索引count=0#总分#只有一张卡牌无需合并if length==1:    count+=a[0]else:    while length>1:        #找到相邻数和最大的一组        for i in range(length-1):            sum_step=a[i]+a[i+1]            if sum_step>max_step:                max_step=sum_step                max_index=i        count+=max_step        #合牌，删除被合并的卡牌        a[max_index]=max_step        a.pop(max_index+1)        length=len(a)        print(a)print(count)

本站内容未经许可，禁止任何网站及个人进行转载。