题解：P12823 [NERC 2021] Job Lookup

· · 题解

区间 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;
}