MLE求助
查看原帖
MLE求助
94712
我的天空楼主2022/9/22 00:56

不知道为啥MLE了,是因为1多了dp太深吗

#include <bits/stdc++.h>
using namespace std;
int data[500010][3],num=0,min1[500010][3],max1[500010][3],ansmax=-1,ansmin=500010;
char tree[500010];
void build_tree(){
	int now=num;
	if(tree[num]=='1'){
		data[num][0]=1;
		data[num][1]=++num;
		build_tree();
	}
	if(tree[num]=='2'){
		data[num][0]=2;
		data[num][1]=++num;
		build_tree();
		data[now][2]=++num;
		build_tree();
	}
	return ;
}
void dp(int i,int m){
	if(min1[i][m]==-1){
		for(int j=1;j<=data[i][0];++j)for(int k=0;k<3;++k)if(k!=m)dp(data[i][j],k);
		int ans=500010;
		if(data[i][0]==0)ans=0;
		if(data[i][0]==1)for(int k=0;k<3;++k)if(k!=m)ans=min(ans,min1[data[i][1]][k]);
		if(data[i][0]==2){
			if(m==0)ans=min(min1[data[i][1]][1]+min1[data[i][2]][2],min1[data[i][1]][2]+min1[data[i][2]][1]);
			if(m==1)ans=min(min1[data[i][1]][0]+min1[data[i][2]][2],min1[data[i][1]][2]+min1[data[i][2]][0]);
			if(m==2)ans=min(min1[data[i][1]][1]+min1[data[i][2]][0],min1[data[i][1]][0]+min1[data[i][2]][1]);
		}
		if(m==1)ans++;
		min1[i][m]=ans;
	}
	if(max1[i][m]==-1){
		for(int j=1;j<=data[i][0];++j)for(int k=0;k<3;++k)if(k!=m)dp(data[i][j],k);
		int ans=-1;
		if(data[i][0]==0)ans=0;
		if(data[i][0]==1)for(int k=0;k<3;++k)if(k!=m)ans=max(ans,max1[data[i][1]][k]);
		if(data[i][0]==2){
			if(m==0)ans=max(max1[data[i][1]][1]+max1[data[i][2]][2],max1[data[i][1]][2]+max1[data[i][2]][1]);
			if(m==1)ans=max(max1[data[i][1]][0]+max1[data[i][2]][2],max1[data[i][1]][2]+max1[data[i][2]][0]);
			if(m==2)ans=max(max1[data[i][1]][1]+max1[data[i][2]][0],max1[data[i][1]][0]+max1[data[i][2]][1]);
		}
		if(m==1)ans++;
		max1[i][m]=ans;
	}
}
int main(){
	freopen("test.in","r",stdin);
	scanf("%s",&tree);
	build_tree();
	memset(min1,-1,sizeof(min1));
	memset(max1,-1,sizeof(max1));
	for(int k=0;k<3;++k)dp(0,k);
	for(int k=0;k<3;++k){
		ansmin=min(ansmin,min1[0][k]);
		ansmax=max(ansmax,max1[0][k]);
	}
	printf("%d %d",ansmax,ansmin);
	return 0;
} 
2022/9/22 00:56
加载中...