TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4970
  • Problem
  • P4970合并石子(加强版)
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s 512m
    Description

    从前有$n$堆石子,每堆石子有$a_i$颗,现在需要将其合并为一堆。 每次只能合并相邻的两堆石子,定义一次合并的代价为所选两堆石子的总和,求最小总代价。

    Input Format

    两行

    第一行一个正整数$n$

    第二行$n$个正整数$a_i$

    Output Format

    一行,表示答案

    Sample Input

    5
    8 6 6 1 2 

    Sample Output

    49

    Hint

    对于所有数据$n\leq5000,a_i\leq10^6$


    Source  感谢OBlack放题