p1880 [noi1995] 石子合并

题目描述

有n堆石子排成一排，每堆石子有一个权值。每次可以将相邻的两堆石子合并，合并后的新堆的权值为原来两堆的权值和，花费为原来两堆的权值和。可以不断地进行合并操作，直到所有石子都合并成为一堆。求最小的花费。

输入格式

第一行一个整数n，表示石子的堆数。

第二行n个整数，表示每堆石子的权值。

输出格式

输出一个整数，表示最小的花费。

数据范围

1≤n≤100

输入样例

4
1 2 3 4

输出样例

19

算法1

(动态规划) $O(n^3)$

状态表示：f[i][j]表示将第i到第j堆石子合并成一堆的最小花费

状态转移：f[i][j]=min(f[i][k]+f[k+1][j]+sum[i][j]) (i<=k<j)

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(贪心) $O(n^2)$

时间复杂度

参考文献

C++ 代码