专栏文章

题解：P12823 [NERC 2021] Job Lookup

FFS_NEO
P12823题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip1paq8
此快照首次捕获于
2025/12/03 04:43
3 个月前
此快照最后确认于
2025/12/03 04:43
3 个月前
查看原文
区间 DP 板题。
题目要求建立一颗二叉搜索树，很容易想到以编号为下标，进行区间 DP。
设 costi,jcost_{i,j} 表示编号在 [i,j][i,j] 区间内所有节点，与区间外所有节点的消息数量和；fi,jf_{i,j} 表示将 [i,j][i,j] 区间内的点建树花费的最小代价，容易得到转移：
f[i][j]=min⁡  k∈[i,j]  ( f[i][k−1]+f[k+1][j]+cost[i][k−1]+cost[k+1][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(n3)O(n^3)，细节处理见代码：
CPP
/*

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

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...