当dfs时直接输出答案会炸掉 如下代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int len,ans=0x3f3f3f3f;
int a[1000100],sum[1000100];
char t[1000100],s[1000100];

bool check(){
	memset(sum,0,sizeof sum);
	for(int i=1;i<=len;++i) sum[i]=sum[i-1]+a[i];
	if(sum[len]==len||sum[len]==0) return true;
	int l;
	for(int i=1;i<=len;++i){
		if(sum[i]==1) l=i-1;
		if(sum[len]-sum[l]==len-l) return true;
	}
	return false;
}

void dfs(int now,int sum){ 
	if(now==len){
		if(check()) ans=min(ans,sum);
		return;
	}
	if(a[now]==0){
		dfs(now+1,sum);
		a[now]=1;
		dfs(now+1,sum+1);
		a[now]=0;
	}
	else{
		dfs(now+1,sum);
		a[now]=0;
		dfs(now+1,sum+1);
		a[now]=1;
	}
}

int main(){
	cin>>t;
	len=strlen(t);
	for(int i=0;i<len;++i) s[i+1]=t[i];
	for(int i=1;i<=len;++i) a[i]=s[i]-'0';
	dfs(1,0);
	cout<<endl<<endl<<ans;
	
	return 0;
}

但是 如果在dfs中输出一个数后 不会炸掉并且可以输出最后的答案 如下

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int len,ans=0x3f3f3f3f;
int a[1000100],sum[1000100];
char t[1000100],s[1000100];

bool check(){
	memset(sum,0,sizeof sum);
	for(int i=1;i<=len;++i) sum[i]=sum[i-1]+a[i];
	if(sum[len]==len||sum[len]==0) return true;
	int l;
	for(int i=1;i<=len;++i){
		if(sum[i]==1) l=i-1;
		if(sum[len]-sum[l]==len-l) return true;
	}
	return false;
}

void dfs(int now,int sum){ 
	cout<<1<<" ";//输出任意一个数 
	if(now==len){
		if(check()) ans=min(ans,sum);
		return;
	}
	if(a[now]==0){
		dfs(now+1,sum);
		a[now]=1;
		dfs(now+1,sum+1);
		a[now]=0;
	}
	else{
		dfs(now+1,sum);
		a[now]=0;
		dfs(now+1,sum+1);
		a[now]=1;
	}
}

int main(){
	cin>>t;
	len=strlen(t);
	for(int i=0;i<len;++i) s[i+1]=t[i];
	for(int i=1;i<=len;++i) a[i]=s[i]-'0';
	dfs(1,0);
	cout<<endl<<ans;
	
	return 0;
}

输入：1010000101
输出：3

玄学求助