纸箱回收集散

普及-⏱ 1000ms💾 256MB#P3282🏷️ 动态规划区间DP

题目描述

回收站环形摆放着 $n$ 摞纸箱,第 $i$ 摞有 $c_i$ 个纸箱。每次操作只允许合并相邻的两摞, 合并后新摞的箱数为两摞之和,操作成本记为新摞的箱数。全部合并成一摞恰好需要 $n-1$ 次操作。 分别求出总成本的最小值与最大值。

输入格式

第一行一个整数 $n$。 第二行 $n$ 个整数,第 $i$ 个为第 $i$ 摞的箱数 $c_i$(环形排列)。

输出格式

共两行:第一行为总成本最小值,第二行为总成本最大值。

数据范围

None

样例输入 #1
4
4 5 9 4
样例输出 #1
43
54
样例输入 #2
1
7
样例输出 #2
0
0