问题：有编号1-n的节点，以编号为权值建立BST，定义代价为Σf[i]*d[i]，其中f[i]为i节点的权值，d[i]为i在BST上的深度。求所有BST中最小的代价。

 

解决：动态规划问题。动态转移方程为：

                F[i,j]=min(f[i,k-1],f[k+1,j])+w[i,j]  (i<=k<=j)

其中w[i,j]=Σf[k](i<=k<=j)

时间复杂度为O(n^3)

四边形不等式优化（重点）

证明过程略

总之设s[i,j]为区间(i,j)的决策k，则s[i,j-1]<=k<=s[i+1,j]

则时间复杂度降为O(n^2)

Code:

Program MinBST;var	f,s			:		array[1..100,1..100] of longint;	cost,w		:		array[1..100] of longint;	n,i,j,k,l	:		longint;	beg,en,min	:		longint;	fin,fou		:		text;	begin	assign(fin,'minbst.in');	assign(fou,'minbst.out');	reset(fin); rewrite(fou);	readln(fin,n);	for i:=1 to n do 		begin			readln(fin,cost[i]);			w[i]:=w[i-1]+cost[i];		end;	for i:=1 to n do 		begin			f[i,i]:=cost[i];			s[i,i]:=i;		end;			for l:=2 to n do 		for i:=1 to n-l+1 do 			begin				j:=i+l-1;				beg:=s[i,j-1];				en:=s[i+1,j];				min:=maxlongint;				for k:=beg to en do						if f[i,k-1]+f[k+1,j]