WA求调
查看原帖
WA求调
1396153
yinbocheng楼主2025/7/21 20:35
#include<bits/stdc++.h>
using namespace std;
int son[500010][4];
int cnt [500010];
string a;
int len;
int dpx[500010][4];
int dpn[500010][4];
void dfs(int f){
	if(f==-1)return;
	dpx[f][1]=1;
	dpn[f][1]=1;
	dpn[f][0]=0;
	dpn[f][2]=0;
	if(cnt[f]==0)return;
	for(int i=1;i<=cnt[f];i++){
		dfs(son[f][i]);
	}
	dpx[f][0]+=max(dpx[son[f][1]][1]+dpx[son[f][2]][2],dpx[son[f][1]][2]+dpx[son[f][2]][1]);
	dpx[f][1]+=max(dpx[son[f][1]][0]+dpx[son[f][2]][2],dpx[son[f][1]][2]+dpx[son[f][2]][0]);
	dpx[f][2]+=max(dpx[son[f][1]][1]+dpx[son[f][2]][0],dpx[son[f][1]][0]+dpx[son[f][2]][1]);
	dpn[f][0]+=min(dpn[son[f][1]][1]+dpn[son[f][2]][2],dpn[son[f][1]][2]+dpn[son[f][2]][1]);
	dpn[f][1]+=min(dpn[son[f][1]][0]+dpn[son[f][2]][2],dpn[son[f][1]][2]+dpn[son[f][2]][0]);
	dpn[f][2]+=min(dpn[son[f][1]][1]+dpn[son[f][2]][0],dpn[son[f][1]][0]+dpn[son[f][2]][1]);
}
int w=1;
void make(int f){
	if(f==-1)return;
	if(a[f]=='1'){
		cnt[f]=1;
		son[f][1]=w;
		son[f][2]=-1;
		w++;
		make(son[f][1]);
	}
	if(a[f]=='2'){
		cnt[f]=2;
		son[f][1]=w;
		w++; 
		make(son[f][1]);
		son[f][2]=w;
		w++;
		make(son[f][2]);
	}
}
int main(){
	memset(dpn,0x3f,sizeof(dpn));
	cin>>a;
	len=a.size();
	make(0);
	dfs(0);
	cout<<max(dpx[0][0],max(dpx[0][1],dpx[0][2]))<<" ";
	cout<<min(dpn[0][0],min(dpn[0][1],dpn[0][2]));
} 
2025/7/21 20:35
加载中...