本文出自 http://blog.csdn.net/shuangde800
------------------------------------------------------------------------------------------------
题意
给一个序列即可 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}
代码
<script src="https://code.csdn.net/snippets/859.js" type="text/javascript"></script>
分享到:
相关推荐
最小成本二分检索树optimal binary optimal binary
关于最优二叉查找树的开山之作,介绍了最优二叉查找树的概念,以及构造最优二叉查找树的动态规划算法,来自D. E. KNUTH,发表于1971年,亦可从这里下载:...
最优二叉搜索树算法,Optimal binary search tree algorithm
Construct Optimal Binary Search Tree by Using Greedy Algorithm
Multi-sensor optimal information fusion Kalman filter 卡尔曼滤波
Build an optimal binary search tree using dynamic programming.
this is optimal binary search tree!! my masterpiece works!!
This file with name "Binary search tree.cpp" create optimal binary search tree
H-Inf Optimal Control
Yuan 等。 - 2017 - Time Optimal Contouring Control of Industrial Biax1
经济管理学前沿期刊 4-1Optimal capacity allocation in multi-auction electricity markets under uncertainty.pdf
Real-time Optimal Control (ECMS) of Hybrid Electric Powertrains
MIT Press - Applied Optimal Estimation [Gelb, 16th Printing, Scan, OCR] - 2001 - (By Laxxuss),一本很不错书,找了好久才找到的。
基于学习的储能定价者最优市场竞价策略_A Learning-based Optimal Market Bidding Strategy for Price-Maker Energy Storage.pdf
Patch-based Near-Optimal Image Denoising http://users.soe.ucsc.edu/~priyam/PLOW/download.php
sgowris2-inverse-optimal-control.zip
Optimal Binary Training Sequence Design for multiple-antenna systems over dispersive fading channels 分享论文
Unit-4-Optimal-Design-机电专业英语-图文课件.ppt
前端项目-optimal-select,为HTML元素获取高效、健壮的CSS选择器
Knowledge and mathematical programming-based optimal scheduling for byproduct gas system in steel industry