金题大战Vol.0 D、二叉搜索树

题目描述

有(n)个结点，第(i)个结点的权值为(i)。

你需要对它们进行一些操作并维护一些信息，因此，你需要对它们建立一棵二叉搜索树。在整个操作过程中，第(i)个点需要被操作(x_i)次，每次你需要从根结点一路走到第(i)个点，耗时为经过的结点数。最小化你的总耗时。

输入格式

第一行一个整数(n)，第二行(n)个整数(x1-xn)。

输出格式

一行一个整数表示答案。

样例

样例输入

5
8 2 1 4 3

样例输出

35

数据范围与提示

对于(10\%)的数据，(n<=10)。

对于(40\%)的数据，(n<=300)。

对于(70\%)的数据，(n<=2000)。

对于(100\%)的数据，(n<=5000，1<=x_i<=10^9)。

提示：二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

分析

我们可以这样想，在一个二叉搜索树中，一个节点左儿子的权值一定小于该节点的权值，一个节点右儿子的权值一定大于该节点的权值

因此，我们可以把连续的一段区间看成一个子树，枚举区间中的节点作为根节点

我们发现这就是一个区间(DP)

状态转移方程为 (f[l][r]=f[l][k-1]+f[k+1][r]+sum[r]-sum[l-1])

用四边形不等式可以优化到(n^2)

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
typedef long long ll;
ll f[maxn][maxn],sum[maxn];
int g[maxn][maxn],a[maxn];
inline int read(){
	register int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int main(){
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
	register int n;
	n=read();
	for(register int i=1;i<=n;i++){
		a[i]=read();
		sum[i]=sum[i-1]+a[i];
		g[i][i]=i;
		f[i][i]=a[i];
	}
	for(register int d=2;d<=n;d++){
		for(register int l=1;l<=n-d+1;l++){
			register int r=l+d-1;
			f[l][r]=0x3f3f3f3f3f3f3f3f;
			for(register int k=g[l][r-1];k<=g[l+1][r];k++){
				if(f[l][r]>f[l][k-1]+f[k+1][r]+sum[r]-sum[l-1]){
					f[l][r]=f[l][k-1]+f[k+1][r]+sum[r]-sum[l-1];
					g[l][r]=k;
				}
			}
		}
	}
	printf("%lld
",f[1][n]);
	return 0;
}