n^2 logn暴力dp为什么会寄??
  • 板块P2018 消息传递
  • 楼主Kniqht
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/4 06:33
  • 上次更新2023/11/4 10:23:30
查看原帖
n^2 logn暴力dp为什么会寄??
315205
Kniqht楼主2023/11/4 06:33

样例都过不去,我手模也感觉没问题啊??真的懵逼了,甚至都没写换根

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=1010,M=1e4+10;
int n,f[N],res[N]; 
int stk[N];
int tt;
int h[M],e[M],ne[M],idx;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa){
	tt=0;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u);
		stk[++tt]=f[j];
	}
	sort(stk+1,stk+tt+1);
	for(int i=1;i<=tt;i++)
		f[u]=max(f[u],stk[i]+tt-i+1);
}
signed main(){
	memset(h,-1,sizeof(h));
	int u;scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d",&u);
		add(u,i);add(i,u);
	}
	for(int i=1;i<=n;i++){
		memset(f,0,sizeof(f));
		dfs(i,-1);
		res[i]=f[i];
	}
	int ans=2e9;
	for(int i=1;i<=n;i++) ans=min(ans,res[i]);
	printf("%d\n",ans+1);
	for(int i=1;i<=n;i++)
		if(res[i]==ans) printf("%d ",i);	
    return 0;   
}
2023/11/4 06:33
加载中...