首页 > 试题广场 >

石子合并

[编程题]石子合并

热度指数：4046 时间限制：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

输出

算法知识视频讲解

Java

ZLMing

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int sum = 0;
        int num = arr[0];
        for(int i=1;i<n;i++){
            sum = sum+arr[i]*num;
            num = num + arr[i];
        }
        System.out.println(sum);
    }
}

发表于 2019-01-15 18:38:40 回复(0)