[题目通道](【XR-4】复读 - 洛谷)

#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;struct ed{int ls,rs,f,sz,dd;
}p[3000],c[3000];
string s;
int st,lq,ans=inf/2;int build(int fa,int poi){p[poi].f=fa; p[poi].sz=1; p[poi].dd=p[fa].dd+1; if (s[poi]=='3') {p[poi].ls=build(poi,poi+1), p[poi].sz+=p[p[poi].ls].sz;p[poi].rs=build(poi,poi+p[poi].sz), p[poi].sz+=p[p[poi].rs].sz;}if (s[poi]=='2') p[poi].rs=build(poi,poi+1), p[poi].sz+=p[p[poi].rs].sz;if (s[poi]=='1')p[poi].ls=build(poi,poi+1), p[poi].sz+=p[p[poi].ls].sz;return poi;
}int gd(int now,string t)
{	int l=t.size();for (int i=0;i<l;i++) now=((t[i]=='L')?p[now].ls:p[now].rs);return now;
}int merge(int now,int cs,int sp){	if (!now) return cs;if (!cs) cs=++st; c[cs].sz=1;if (now==sp) return cs;c[cs].ls=merge(p[now].ls,c[cs].ls,sp); c[cs].sz+=c[c[cs].ls].sz;c[cs].rs=merge(p[now].rs,c[cs].rs,sp); c[cs].sz+=c[c[cs].rs].sz;return cs;
}int find(string rep)
{int now=1,last=0;while (now){ last=now , now=gd(now,rep); merge(last,1,now);}return c[1].sz;
}void search(int now,string rep){  int cnt=0;if (now==0) return;if (now!=1) {memset(c,0,sizeof(c)); st=1; cnt=find(rep);ans=min(ans,2*(cnt-1)-p[now].dd+1);}search(p[now].ls,rep+'L');search(p[now].rs,rep+'R');
}int main()
{cin>>s; lq=s.size(); s='.'+s; build(0,1);search(1,"");cout<<ans<<endl;
}