不难发现题目要求构造的树是一颗二叉搜索树，于是考虑在升序排列上构造
考虑谁作为树根，不难发现这个过程很像区间DP，设当前枚举的树根为\(l\)，我们只要能够\(O(1)\)计算\([1,l-1]\)和\([l+1,n]\)中间的贡献就可以转移了
当然还要消除后效性，于是考虑分配花费。不难想到类似树上染色的分配方案，于是做如下分配：假设已经确定了最终的树，对于两个点\(u,v\)，他们的花费是\(d_{uv}\cdot c_{uv}\)，我们将\(u\)到\(v\)的每一条边的贡献加上\(c_{uv}\)，于是最终的总花费等于这棵树所有边的贡献之和
于是就可以进行DP转移了。设\(f[l][r]\)表示将区间\([l,r]\)构建成一颗BST，其所有边的最小贡献。枚举根节点\(k\)，则\(f[l][r]=\min(f[l][k-1]+f[k+1][r]+cost_1+cost_2)\)，其中\(cost_1\)表示\([l,k-1]\)的所有点与除了\([l,k-1]\)之外的点构建联系所经过的\(k\)与其左子节点的边的花费，\(cost_2\)类似
形式化地，$$cost_1=\sum_{i=l}^{k-1}sum_{i,l-1}+sum_{i,n}-sum_{i,k-1}$$，其中
\[sum_{i,j}=\sum_{k=1}^{j}c[i][k] \] 标签：于是,花费,sum,uv,贡献,Job,cost,Lookup From： https://www.cnblogs.com/dingxingdi/p/18343143