一开始我dfs时用的是构造二叉树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500010;
ll dp[MAXN][4][2];
ll edge=1;
char c;
//21200110
//222002002200200
void dfs(ll x)
{
	scanf(" %c",&c);
	ll t=c-'0';
	if(t>=1)
	dfs(x*2);
	if(t==2)
	dfs(x*2+1);
	dp[x][1][1]=max(dp[x*2][3][1]+dp[x*2+1][2][1],dp[x*2][2][1]+dp[x*2+1][3][1])+1;
	dp[x][2][1]=max(dp[x*2][1][1]+dp[x*2+1][3][1],dp[x*2][3][1]+dp[x*2+1][1][1]);
	dp[x][3][1]=max(dp[x*2][1][1]+dp[x*2+1][2][1],dp[x*2][2][1]+dp[x*2+1][1][1]);
	dp[x][1][0]=min(dp[x*2][3][0]+dp[x*2+1][2][0],dp[x*2][2][0]+dp[x*2+1][3][0])+1;
	dp[x][2][0]=min(dp[x*2][1][0]+dp[x*2+1][3][0],dp[x*2][3][0]+dp[x*2+1][1][0]);
	dp[x][3][0]=min(dp[x*2][1][0]+dp[x*2+1][2][0],dp[x*2][2][0]+dp[x*2+1][1][0]);
}
int main()
{
	dfs(1);
	ll Max=max(dp[1][1][1],max(dp[1][2][1],dp[1][3][1]));
	ll Min=min(dp[1][1][0],max(dp[1][2][0],dp[1][3][0]));
	printf("%lld %lld",Max,Min);
	return 0;
}
然而我只有20分，其他RE，因为爆空间了。
就是如果那个字符串是5乘10的5次，就要开
2的5乘10的5次方的大小的空间
但是不一定要构造二叉树
可以
dfs(x+1),dfs(x+2)而不是dfs(x*2)、dfs(x*2+1)
但是这样的话，你模拟一下就会发现，
第二次调用同一个，比如说dfs(3)时，
上一次的dp数组留下来就会导致这一次求dp出问题
（可以自己模拟一下，我相信各位一定能发现的）
所以上一次赋值完了以后，要清零
就像这样

dp[x+1][1][1]=dp[x+1][2][1]=dp[x+1][3][1]=dp[x+2][1][1]=dp[x+2][2][1]=dp[x+2][3][1]=dp[x+1][1][0]=dp[x+1][2][0]=dp[x+1][3][0]=dp[x+2][1][0]=dp[x+2][2][0]=dp[x+2][3][0]=0; 我能提供的提醒就这些，其他请自己思考