#P1880. [NOI1995] 石子合并

    ID: 775 远端评测题 1000ms 125MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>动态规划dp2001NOI 系列区间 dp四边形不等式

[NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放 NN 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 22 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出一个算法,计算出将 NN 堆石子合并成 11 堆的最小得分和最大得分。

输入格式

数据的第 11 行是正整数 NN,表示有 NN 堆石子。

22 行有 NN 个整数,第 ii 个整数 aia_i 表示第 ii 堆石子的个数。

输出格式

输出共 22 行,第 11 行为最小得分,第 22 行为最大得分。

4
4 5 9 4
43
54

提示

1N1001\leq N\leq 1000ai200\leq a_i\leq 20