题解：AT_agc055_d [AGC055D] ABC Ultimatum

· · 题解

来点正推。

这和 AGC066C 有点像。先考虑一个串能否被划分。先来看看能不能判定划分为 \texttt{AB},\texttt{BC},\texttt{CA}。设这三种出现次数为 a,b,c，这是可以计算的。那么，必然 \texttt{A} 的前 a 个用于填充 \texttt{AB}，后 c 个用于填充 \texttt{CA}，其他同理。这可以得到简单判定。这个判定是，把前 b 个 \texttt{A} 视为 +1，后 b 个 \texttt{B} 视为 -1，是否有前缀和始终非负（还有同样的两组）。考虑第 i 个 A 的前面最接近的 B 是第 j 个加以判定即可。

我们来看看是否对 \texttt{ABC},\texttt{BCA},\texttt{CAB} 也有类似结构，依旧设为 a,b,c，只不过 a,b,c 不能直接计算得到。

我们考虑向 \texttt{A},\texttt{C} 构成的子序列里面插入 \texttt{B}。这里就得到 b 个 \texttt{B} 用于 \texttt{BCA} 在前面，c 个 \texttt{B} 用于 \texttt{CAB} 在后面，中间是 a 个 \texttt{B} 用于 \texttt{ABC}，否则可以调整：

例如 \texttt{ABCBCA}，若采取 \{1,2,3\} 和 \{4,5,6\} 配对，即用于 \texttt{ABC} 的 \texttt{B} 在 \texttt{BCA} 前面，则可调整为 \{1,4,5\} 和 \{2,3,6\} 配对。

这样就了解了答案的结构：

只需判定每个箭头是否可分别实现。拿 \texttt{B} 为例子，设第 i 个 B 的前面最接近的 A 是第 j 个。对于第二段的 a 个，要求 j\ge i-b，第三段要求 j-a\ge i-a-b，这实际上就是要求

\forall i,i-j\le b

同理有 \texttt{A},\texttt{C} 的限制。由于 a,b,c 是我任意指定的，那么我就是要求（这里写法可能不规范，意思应该能理解；如果不能理解，这个式子同其他题解给出的结论。）：

\max i-j+\max j-k+\max k-i\le n

那么直接 dp 记录这三者 \max 和 \texttt{A},\texttt{B},\texttt{C} 个数即可做到 O(n^6)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,B=1e6,INF=1e8;
int g[maxn*3][3][2],f[maxn],n,T,a[maxn],s[maxn];
string str;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>str;n=str.size();
        for(int i=1;i<=n;i++)a[i]=(str[i-1]=='B'?2:-1),s[i]=s[i-1]+a[i];a[n+1]=0;
        for(int i=-n;i<=2*n;i++)for(int j:{0,1,2})for(int k:{0,1})g[i+B][j][k]=-INF;
        f[0]=0;g[s[0]+B][0%3][a[1]==2]=0;int ans=0;
        for(int i=1;i<=n;i++){
            int j=a[i]==2;f[i]=f[i-1];
            for(int k:{0,1})if(j||k)
                f[i]=max(f[i],g[s[i]+B][i%3][k]+i);
            g[s[i]+B][i%3][a[i+1]==2]=max(g[s[i]+B][i%3][a[i+1]==2],f[i]-i);
            ans=max(ans,f[i]);
        }
        cout<<ans/3<<endl;
    }
    return 0;
}

写完才发现和 yzc001的题解 写的是一个过程。作为同样描述了正向推导的过程的题解，希望能给他几个点赞！