UVA10304 Optimal Binary Search Tree(数据加强)

题目描述

给你 $N$ 个数 $e_i$ ，保证输入的数单调递增，这 $N$ 个数如果作为 $N$ 点的点权构成一棵二叉搜索树（中序遍历要递增），那么这棵二叉搜索树的费用就是每一个点的（点权×深度）的和，根节点的深度为0。现在请你求出这个最小的费用。 一句话题意：求一棵有 $N$ 个节点的二叉搜索树，使 $\sum_{i=1}^N e_i×depth_i$ 最小。

输入格式

多组数据。每组数据一行，如下：

第一个整数 $n \ (1 \le n \le 5000)$ ，下来 $n$ 个整数 $e_i \ (0 \le e_i \le 50000)$ 。

输出格式

每组数据输出一行一个整数，表示结果。

输入输出样例 #1

输入 #1

1 5
3 10 10 10
3 5 10 20

输出 #1

0
20
20