不难发现题目要求构造的树是一颗二叉搜索树,于是考虑在升序排列上构造
考虑谁作为树根,不难发现这个过程很像区间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