首页 > 试题广场 >

石子合并

[编程题]石子合并
  • 热度指数：4029 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

小Q和牛博士在玩一个石子合并的游戏，初始一共有n堆石子，每堆石子有w[i]个石子。小Q和牛博士他们需要对石子堆进行合并，每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆，这次合并得分为x*y，当只剩下一堆石子的时候游戏结束。

、小Q和牛博士希望采取优秀的策略获得最大得分，希望你能来帮他们算算最大得分多少。


输入描述:
输入包括两行，第一行一个正整数n(2≤n≤100)。

第二行包括n个正整数w[i](1≤w[i]≤100)，即每堆石子的个数。


输出描述:
输出一个正整数，即小Q和牛博士最大得分是多少。
示例1

输入

3
1 2 3

输出

11
算法知识视频讲解
添加回答
Python
牛客817844335号头像 牛客817844335号
n = int(input())
w = list(map(int,input().split(' ')))
score = 0
while True:
    if len(w) == 1:
        break
    else:
        w = sorted(w,reverse=True)
        l_1 = w.pop(-1)
        l_2 = w.pop(-1)
        score += l_1*l_2
        w.append(l_1+l_2)
print(score)
编辑于 2020-09-06 17:31:09 回复(0)
Python
wangkss_01头像 wangkss_01
原来这个题没必要排序的。。。
说下我思路，不是最优的，但算是一种方法：
1.首先要想分数最高，那么对大的堆一定要用很多次，作为多次因子；
2.另外考虑到递归，就是F(k1,k2,...,kn) = kn*（k1+k2+...+kn-1）+ F(k1,k2,...,kn-1)，其中k1,k2,...,kn是从小到大排序的。
发表于 2020-06-13 22:23:51 回复(0)
Python
lx的流星头像 lx的流星 
while True:
    try:
        n=int(input().strip())
        inp=list(map(int,input().strip().split(' ')))
        #print(inp)
        inp=sorted(inp)
        list1=[]
        while len(inp)!=1:
            sum1=inp[-1]+inp[-2]
            mul=inp[-1]*inp[-2]
            list1.append(mul)
            inp=inp[:-2]+[sum1]
        #print(list1)
        result=sum(list1)
        print(result)
    except:
        break
发表于 2019-07-24 09:28:02 回复(0)
Python
灵鹫听经头像 灵鹫听经
定义一个函数，函数每次先排序w，然后遍历，找到最相近的两个数， 更新得分，在w后添加两数的和，并在原列表中删除两数。上述过程做完后，不用等遍历结束即可推出 （另外；定义函数中找最相近两数时，也是一个遍历过程，循环从0到w的极差） 反复调用函数，每次调用都会合并两个数，即w长度减一，w的长度为1时即可推出循环； 
# 获取输入的数据 n = int(input())
w = list(map(int, input().split())) # 初始化得分为0 score = 0   def cross(w, score): """  定义一个函数，每次调用都会合并w中最接近的两项    :param w:    :param score:    :return:  """    # if n == 1:  #     return w, score  # 对w的预处理，排序；使得最相近的两数相邻    w = sorted(w)  # 求w的极差    gap = max(w)-min(w)  # 寻找最相邻的两数也是一个遍历过程，可能的取值从0到极差    for i in range(gap+1):  # 从头遍历w中的 每个元素，看它与它的前一项是否符合本轮要找的最相近的两数    for j in range(1, len(w)):  if w[j]-w[j-1] == i:  # 当找到最相邻的两数时，更新得分    score += w[j]*w[j-1]  # w得到两数合并之后的新的成员    w.append(w[j] + w[j - 1])  # 除去旧的成员  w.pop(j)
                  w.pop(j-1)     # 只要找到就可以直接推出循环，返回新的w与更新过的score    return w, score while True: # 多次调用函数，直到w长度为1时，推出循环    if len(w) == 1:  break  else:
          w, score = cross(w, score) print(score)
编辑于 2019-07-17 10:31:36 回复(0)
Python
体重不增到120不改名头像 体重不增到120不改名
先排序，想要得分最高，每次都选数量最多的两个堆，这个在数学上可以证明。 
n=int(input())
L=list(map(int,input().split()))
L.sort()
s=0
for i in range(n-1):
    t=L.pop()
    s+=(t*L[-1])
    L[-1]+=t
print(s)

发表于 2019-03-09 16:44:56 回复(0)
提交观点

问题信息

上传者：小小
难度：
7条回答 5529浏览

热门推荐

通过挑战的用户

查看代码

相关试题

石子合并

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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