自动搬运

查看原文

来自洛谷，原作者为

	FS_NEO birb.

搬运于2025-08-24 23:18:14，当前版本为作者最后更新于2025-06-23 19:55:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

区间 DP 板题。

---

题目要求建立一颗二叉搜索树，很容易想到以编号为下标，进行区间 DP。

设 $cost_{i,j}$ 表示编号在 $[i,j]$ 区间内所有节点，与区间外所有节点的消息数量和；$f_{i,j}$ 表示将 $[i,j]$ 区间内的点建树花费的最小代价，容易得到转移：

$$f[i][j]=\min_{\;k\in[i,j]\;}\Bigl(\, f[i][k-1]+f[k+1][j]+\text{cost}[i][k-1]+\text{cost}[k+1][j]\Bigr) $$

记录转移路径即可，时间复杂度 $O(n^3)$，细节处理见代码：

/*

  2025.6.23

 * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
const int MAXN=205,mod=1e9+7,inf=1e17;
int n,a[MAXN][MAXN],cst[MAXN][MAXN];
int f[MAXN][MAXN],ffa[MAXN],g[MAXN][MAXN];
void solve(int l,int r,int fa){
	if(l>r)return ;
	ffa[g[l][r]]=fa;
	if(l==r)return ;
	solve(l,g[l][r]-1,g[l][r]);
	solve(g[l][r]+1,r,g[l][r]);
}
signed main(){
	memset(f,0x3f,sizeof(f));
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)for(int t=i;t<=j;t++)for(int k=1;k<=n;k++)if(k<i||k>j)cst[i][j]+=a[t][k];
	for(int i=1;i<=n;i++)f[i][i]=0,g[i][i]=i;
	for(int l=2;l<=n;l++){
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			if(f[i+1][j]+cst[i+1][j]<=f[i][j])f[i][j]=f[i+1][j]+cst[i+1][j],g[i][j]=i;
			if(f[i][j-1]+cst[i][j-1]<=f[i][j])f[i][j]=f[i][j-1]+cst[i][j-1],g[i][j]=j;
			for(int k=i+1;k<j;k++){
				if(f[i][k-1]+cst[i][k-1]+f[k+1][j]+cst[k+1][j]<=f[i][j]){
					f[i][j]=f[i][k-1]+cst[i][k-1]+f[k+1][j]+cst[k+1][j];
					g[i][j]=k;
				}
			}
		}
	}
	solve(1,n,0);
	for(int i=1;i<=n;i++)cout<<ffa[i]<<" ";
	return 0;
}