题意
给一个序列即可 S = (e1,e2,...,en),且e1<e2<..<en.要把这些序列构成一个二叉搜索 树。
二叉搜索树是具有递归性质的，且若它的左子树不空，则左子树上所有结点的值均小于它的根结点的 值； 若它
的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
因为在实际应用中，被访 问频率越高的元素，就应该越接近根节点，这样才能更加节省查找时间。
每个元素有一个访问频率f(ei) ，当元素位于深度为k的地方，那么花费cost(ei) = k.
所有节点的花费和访问频率乘积之和为：
sum = f(e1)*cost(e1) + f(e2)*cost(e2) + ... + f(en)*cost(en)
我们叫sum值最小的二叉搜索树为最优二叉 搜索树。
按顺序给出集合序列S，和每个元素的频率f(ei)，求sum的最小值
思路
因为他题目给的 序列是从小到大的，那么对于这个序列的任意一个ei,设ei为根节点，
我们可以知道在序列中ei左边的所 有数会构成ei的左子树，ei的右边的所有数会构成
ei的右子树。
那么我们就可以枚举根节点，然后选 择值最小的一种方案。
说到这里，再结合题目的数据范围，那么很容易可以想到就是区间dp了！
设f(i, j)表示序列区间(i, j)的数构成的一棵最优二叉查找树的值，
当枚举根节点ek时，它的左子树 (wi,wi+1,..,wk-1)的所有节点的深度都会增加1,
那么左子树增加sum(w1,w2,...wk-1)
右子树(ek+1, ek+2,..ej)的值也会增加sum(ek+1,ek+2,...,ej).
可以看出，那么总共会增加sum(i, j) - wk
那 么就可以推出状态转移了：
f(i, j) = min{ f(i,k-1)+f(k+1,j)+sum(i, j) - wk | i<=k<=j}
代码
/**=====================================================
* This is a solution for ACM/ICPC problem
*
* @source : uva-10304 Optimal Binary Search Tree
* @description : 区间dp
* @author : shuangde
* @blog : blog.csdn.net/shuangde800
* @email : zengshuangde@gmail.com
* Copyright (C) 2013/09/06 16:37 All rights reserved.
*======================================================*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long int64;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 210;
int n;
int w[MAXN];
int sum[MAXN];
int f[MAXN][MAXN];
int main(){
while (~scanf("%d", &n)) {
sum[0] = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &w[i]);
sum[i] = sum[i-1] + w[i];
}
memset(f, 0, sizeof(f));
for (int d = 2; d <= n; ++d) {
for (int l = 1; l + d - 1 <= n; ++l) {
int r = l + d - 1;
int ans = INF, tot = sum[r] - sum[l-1];
for (int k = l; k <= r; ++k)
ans = min(ans, f[l][k-1] + f[k+1][r] + tot - w[k]);
f[l][r] = ans;
}
}
printf("%d\n", f[1][n]);
}
return 0;
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， search
， 序列
， binary
， 区间
一个
binary search、binary search tree、binarysearch用法、arrays.binarysearch、java binarysearch，以便于您获取更多的相关知识。