AtCoder -arc224_e ABC|AB|A 题解

Solution对于一个字符串SSS设最优解中被删除的字符按原顺序依次拼接得到的字符串TTT为SSS的最优导出串。我们先考虑最优导出串必然满足的结构。将每个删除的字符串e.g.A/AB/ABC\texttt{A/AB/ABC}A/AB/ABC看作一个结点。那么会形成一个森林。例如(A(AB)B(ABC)C)(A(ABC)B(A… \texttt{(A(AB)B(ABC)C)(A(ABC)B(A\dots}(A(AB)B(ABC)C)(A(ABC)B(A…不难看出以下性质每个点对应原串中一个连续段该连续段中首尾字符都属于该点每个点恰好包含111个A\texttt{A}A位于开头从前向后遍历最优导出串的过程等价于按欧拉序分别遍历每棵树由于A,AB,ABC\texttt{A,AB,ABC}A,AB,ABC中前一个是后一个的前缀栈顶结点可以在任何时刻合法弹出考虑使用栈维护在最优导出串上遍历的过程。栈中依次保存当前链上各个节点已经被遍历到的前缀。调整法易证匹配过程满足贪心性质每新增一个字符从当前节点开始尝试加入若失败就弹栈尝试父节点以此类推。现在转而考虑原串。显然原串就是在最优导出串的不同树之间插入了若干个失配的B/C\texttt{B/C}B/C。每个失配字符会把原串分成前后独立的两部分此时栈已经被自动清空。结合性质 4 可知答案即为失配字符数量。由以上论证可知对于任意原串SSS最优导出串的每个字符一定会被删除正确性自然得到保证。Code#includebits/stdc.husingnamespacestd;constintN1e65;inta[N],ans,n,t;chars[N];// 用数字代替所有可能出现的字符串前缀// 1: A// 2: AB// 3: ABCvoidsolve(){cins;nstrlen(s),tans0;for(inti0;in;i)switch(s[i]){caseA:a[t]1;break;caseB:while(ta[t]!1)--t;a[t]1?a[t]2:ans;break;caseC:while(ta[t]!2)--t;a[t]2?--t:ans;}coutans\n;}signedmain(){intT;cinT;while(T--)solve();return0;}