题解
水DP。
分别给每个点设3个状态即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
char s[10005];
int n,l[10005]={0},r[10005]={0},ans,f[10005][3],o;
int dfs(int cur){
if(s[cur]=='0')return cur;
if(s[cur]=='1'){
l[cur]=cur+1;
return dfs(cur+1);
}
if(s[cur]=='2'){
l[cur]=cur+1;
int t=dfs(cur+1);
r[cur]=t+1;
return dfs(t+1);
}
}
int dfs2(int cur){
if(l[cur])dfs2(l[cur]);
if(r[cur])dfs2(r[cur]);
if(l[cur]&&r[cur]){
if(!o){
f[cur][0]=max(f[l[cur]][1]+f[r[cur]][2],f[l[cur]][2]+f[r[cur]][1]),
f[cur][2]=max(f[l[cur]][1]+f[r[cur]][0],f[l[cur]][0]+f[r[cur]][1]),
f[cur][1]=max(f[l[cur]][0]+f[r[cur]][2],f[l[cur]][2]+f[r[cur]][0])+1;
}else{
f[cur][0]=min(f[l[cur]][1]+f[r[cur]][2],f[l[cur]][2]+f[r[cur]][1]),
f[cur][2]=min(f[l[cur]][1]+f[r[cur]][0],f[l[cur]][0]+f[r[cur]][1]),
f[cur][1]=min(f[l[cur]][0]+f[r[cur]][2],f[l[cur]][2]+f[r[cur]][0])+1;
}
}else if(l[cur]){
if(!o){
f[cur][0]=max(f[l[cur]][1],f[l[cur]][2]),
f[cur][2]=max(f[l[cur]][1],f[l[cur]][0]),
f[cur][1]=max(f[l[cur]][0],f[l[cur]][2])+1;
}else{
f[cur][0]=min(f[l[cur]][1],f[l[cur]][2]),
f[cur][2]=min(f[l[cur]][1],f[l[cur]][0]),
f[cur][1]=min(f[l[cur]][0],f[l[cur]][2])+1;
}
}else{
f[cur][0]=f[cur][2]=0,f[cur][1]=1;
}
}
void init(){
scanf("%s",s+1);
n=strlen(s+1),dfs(1);
}
void solve(){
ans=0,o=0,dfs2(1);
ans=max(ans,max(f[1][0],max(f[1][1],f[1][2])));
printf("%d ",ans);
memset(f,0,sizeof(f));
ans=INF,o=1,dfs2(1);
ans=min(ans,min(f[1][0],min(f[1][1],f[1][2])));
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}