二叉搜索树 [四边形不等式优化区间dp]
二叉搜索树 [四边形不等式优化区间dp]
题目描述
有 \(n\) 个结点，第 \(i\) 个结点的权值为 \(i\) 。
你需要对它们进行一些操作并维护一些信息，因此，你需要对它们建立一棵二叉搜索树。在整个操作过程中，第i个点需要被操作 \(x_i\) 次，每次你需要从根结点一路走到第 \(i\) 个点，耗时为经过的结点数。最小化你的总耗时。
输入格式
第一行一个整数 \(n\) ，第二行 \(n\) 个整数 \(x_1\to x_n\)。
输出格式
一行一个整数表示答案。
样例
样例输入
5
8 2 1 4 3
样例输出
35
数据范围与提示
对于 \(10\%\) 的数据，\(n\leqslant 10\)。
对于 \(40\%\) 的数据，\(n\leqslant 300\)。
对于 \(70\%\) 的数据，\(n\leqslant 2000\)。
对于 \(100\%\) 的数据，\(n\leqslant 5000，1\leqslant x_i\leqslant 10^9\)。
提示：二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
分析
第一眼看上去发现自己不会建二叉排序树了，直接写暴力……，仔细想一想，二叉排序树的性质就是左子树都比根小，右子树都比根大，那么就可以把大区间 \([L,R]\) 通过根节点 \(k\) 分成两部分，然后这里就是一个几乎是裸的区间 \(dp\) 的板子了。
在更新 \(f[i][j]\) 的时候，因为 \([i,j]\) 这一段之间的每个节点都要多经过一个节点，所以要加上整棵树的值，而这用前缀和就可以维护。完结！
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
using namespace std;
#define ll long long
const int maxn = 5e3+10;
ll f[maxn][maxn];
int g[maxn][maxn];
ll sum[maxn];
int a[maxn];
inline ll read(){//快读
ll s = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch = getchar();}
return s * f;
}
int main(){
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
ll n = read();
for(re int i = 1;i<=n;++i){//预处理
a[i] = read();
f[i][i] = a[i];//记录值
g[i][i] = i;//记录决策点（四边形不等式优化）
sum[i] = sum[i-1] + a[i];//前缀和
}
//以下是区间dp
for(re int l = n-1;l >= 1;--l){
for(re int r = l+1;r <= n;++r){
f[l][r] = 0x3f3f3f3f3f3f3f3f;//初始化极大值
for(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\n",f[1][n]);//输出最后的答案
return 0;
}
