首页 > 试题广场 >

石子合并

[编程题]石子合并
  • 热度指数：4041 时间限制：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
算法知识视频讲解
开通博客
头像 白伟仝
发表于 2020-06-29 11:02:15
排序后，从大到小挨着合并就行了。数学证明：无论怎么合并，展开括号后，都有n*(n-1)/2项多项式，且就是每个数分别乘其它各个数，除以2去重。 import java.util.*; public class Main{ public static void main(String[] ar 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 秦时明月2022
发表于 2022-08-12 17:07:41
解题思路 1.可证明任意合并顺序所获得分均一样,简单模拟即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int&g 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-03-22 12:36:58
import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Sc 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 久81
发表于 2022-06-02 10:57:18
与其他人的没什么区别，只是用stream import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scan 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-29 13:45:41
解题思路 题目描述： 堆石子，每堆石子数量为 每次可以选择两堆合并，得分为两堆石子数量的乘积 求最大可能得分 解题策略： 观察发现，无论合并顺序如何，最终得分是所有可能的两两组合的乘积之和 因为每次合并后的新堆石子数量是加法，而得分是乘法 所以合并顺序不影响最终结果 代码 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 olddog#23
发表于 2022-10-27 16:53:28
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyn 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

上传者：小小
难度：
23条回答 5712浏览

热门推荐

通过挑战的用户

查看代码

相关试题

石子合并

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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