2020.07.12日常总结——四边形不等式优化的好题

$\color{green}{\texttt{UVA10304 Optimal Binary Search Tree}}$UVA10304 Optimal Binary Search Tree

$\color{blue}{\texttt{[Problem]}}$[Problem]

最优排序二叉树问题（OBST，全称如题）的模板题。

给定 $n$n 个点的点权 $d_{i}(1 \leq i \leq n)$di​(1≤i≤n)，你需要给它们建一棵排序二叉树，记第 $i$i 个点的深度为 $p_{i}(1 \leq i \leq n)$pi​(1≤i≤n)，要求这棵排序二叉树：

$\sum\limits_{i=1}^{n} p_i \times d_i$i=1∑n​pi​×di​

的值最小。这个值我们称为最小检索次数。

注意，输入平衡树的高度最小，但是它不一定是最优的（甚至可能不如一条链优）。

保证 $d_{i} \leq d_{i+1}(1 \leq i <n)$di​≤di+1​(1≤i<n)。

$\color{blue}{\texttt{[Soluntion]}}$[Soluntion]

我们可以先确定根，再确定左右子树，因为题目保证有序，所以这样做是肯定对的。

记 $f_{i,j}$fi,j​ 表示为区间 $(i,j)$(i,j) 建一棵排序二叉树的最小检索次数。考虑如何计算它。

假设 $k(i \leq k \leq j)$k(i≤k≤j) 为根，它的深度为 $0$0，贡献为 $0 \times d_k=0$0×dk​=0。左子树 $(i,k-1)$(i,k−1) 在单独作为一棵树时的最小检索次数为 $f_{i,k-1}$fi,k−1​，但是因为现在的根是 $k$k 了，所以它们各自的深度都增加了 $1$1，所以总的检索次数要加上：

$d_{i}+d_{i+1}+d_{i+2}+\cdots +d_{k-1}=\sum\limits_{t=i}^{k-1} d_t$di​+di+1​+di+2​+⋯+dk−1​=t=i∑k−1​dt​

右子树类似，记 $c_{i,j}=\sum\limits_{t=i}^{j} d_t$ci,j​=t=i∑j​dt​，则我们有如下转移式：

$\begin{aligned} f_{i,j}&=\min\{f_{i,k-1}+f_{k+1,j}+c_{i,j}-d_{k}\} \\ &=\min\{f_{i,k-1}+f_{k+1,j}-d_{k}\}+c_{i,j}\\ (&i \leq k \leq j) \end{aligned}$fi,j​(​=min{fi,k−1​+fk+1,j​+ci,j​−dk​}=min{fi,k−1​+fk+1,j​−dk​}+ci,j​i≤k≤j)​

直接转移是 $O(n^3)$O(n3) 的，可以用四边形不等式优化到 $O(n^2)$O(n2)，详见参考代码。

$\color{blue}{\texttt{[code]}}$[code]

int w[260][260],e[260];
int n,f[260][260],p[260];
inline int cost(int a,int b,int c){
	return p[b]-p[a-1]-e[c];
}
int main(){
//	freopen("t1.in","r",stdin);
	while (~scanf("%d",&n)&&n){
		memset(p,0,sizeof(p));
		memset(w,0,sizeof(w));
		memset(f,127,sizeof(f));
		for(int i=1;i<=n;i++){
			scanf("%d",&e[i]);
			p[i]=p[i-1]+e[i];
		}
		for(int i=1;i<=n;i++)
			f[i][i]=0,w[i][i]=i;
		for(int i=1;i<=n;i++)
			f[i+1][i]=f[i][i-1]=0;
		for(int L=2;L<=n;L++)
			for(int j=L;j<=n;j++){
				register int i=j-L+1;
				for(int k=w[i][j-1];k<=w[i+1][j];k++)
					if (f[i][k-1]+f[k+1][j]+cost(i,j,k)<=f[i][j]){
						f[i][j]=f[i][k-1]+f[k+1][j]+cost(i,j,k);
						w[i][j]=k;//四边形不等式中的记录决策点 
					}
			}
		printf("%d\n",f[1][n]);
	}
	return 0;
}