试题 算法训练 石子游戏

问题描述
  石子游戏的规则如下:
地上有n堆石子,每次操作可选取两堆石子(石子个数分别为x和y)并将它们合并,操作的得分记为(x+1)×(y+1),对地上的石子堆进行操作直到只剩下一堆石子时停止游戏。
请问在整个游戏过程中操作的总得分的最大值是多少?
输入格式
  输入数据的第一行为整数n,表示地上的石子堆数;第二行至第n+1行是每堆石子的个数。
输出格式
  程序输出一行,为游戏总得分的最大值。
样例输入
10
5105
19400
27309
19892
27814
25129
19272
12517
25419
4053
样例输出
15212676150
数据规模和约定
  1≤n≤1000,1≤一堆中石子数≤50000
思路:解决该问题可以优先考虑贪心算法,类似于这种比较大小取最大值,且满足贪心策略即可。
代码如下
if __name__ == '__main__':
    n = int(input())
    list1 = []
    grade = 0
    for i in range(n):
        x = input()
        list1.append(int(x))    
    list1.sort(reverse=True)
    for j in range(n - 1):
        grade += (list1[0] + 1) * (list1[j + 1] + 1)  # 依次将最大值和最大次值比较
        list1[0] = list1[0] + list1[j + 1]
    print(grade)
点赞
  1. 2222说道:

    大佬,别学啦!!!

  2. 2222说道:

    跟不上啦!!!!!!!!

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00