前言：比赛前去做牙齿矫正，回来晚了 10 分钟……做比赛的运气全用在了一路绿灯上了（无语）。第二题切了两个半小时。决定写篇题解来抒发一下再记得愤怒愉悦之情。
AC 的想法很简单，就是表示出每一串连续的 \(\texttt{T}\)，其长度分别为 \(l_1 \lim l_m\)。明显的，对于任何一个 \(l_i\)，在一系列操作后，它的长度顶多加 \(2\)，也就是左边多一个，右边多一个。明显的贪心，将 \(\texttt{T}\) 子串按长度从大到小排，然后只要枚举到 \(l_i < ans-1\)，就可以结束了。因为它既是加两个，也只能等于 \(ans\)。然后每次更新 \(ans\)。
对于判断左右是否能增加一个，不是只判断有没有 \(\texttt{BTTB}\) 那么简单。拿左边来说，他可能长这样：
\[\texttt{(BTTBTBTBTB)TTTTTTT}
\]
他可以一路猛操作变成：
\[\texttt{(TBBTBTBTBT)TTTTTTT}
\]
我吗，蠢蠢地使用了暴力，然后喜提 \(2\mathcal{WA}+4\mathcal{TLE}\)。加个记忆化，喜提 \(2\mathcal{WA}\)。
为什么呢？因为这个样例：\(1 \texttt{B}\)，要特判一下。（大概也只有我会漏掉这个样例的情况吧，悲。）
\(\mathcal{AC} \texttt{CODE}\)：
#include <bits/stdc++.h>
using namespace std;
int T,n,cnt;
struct Node {
int l,r,mm;
Node(int L=0,int R=0,int m=0) {
l=L,r=R,mm=m;
return ;
}
friend bool operator <(const Node a,const Node b) {
return a.mm>b.mm;
}
};
const int MS=100005;
Node node[MS];
char s[MS];
int pr[MS][2];
bool GO(int p,int drct) {
if(p<1||p>n-1) return 0;
if(pr[p][drct-1]!=-1) return pr[p][drct-1];
if(drct&1) {
if(p>2&&s[p]=='B'&&s[p-1]=='T'&&s[p-2]=='T'&&s[p-3]=='B') return pr[p][drct-1]=true;
if(s[p]=='B'&&s[p-1]=='T') return pr[p][drct-1]=GO(p-2,drct);
}
else {
if(p<n-3&&s[p]=='B'&&s[p+1]=='T'&&s[p+2]=='T'&&s[p+3]=='B') return pr[p][drct-1]=true;
if(s[p]=='B'&&s[p+1]=='T') return pr[p][drct-1]=GO(p+2,drct);
}
return pr[p][drct-1]=false;
}
int main() {
scanf("%d",&T);
while(T--) {
memset(pr,-1,sizeof(pr));
scanf("%d%s",&n,s);
int l=-1;
cnt=0;
for(int i=0;i<n;i++) {
if(s[i]=='B'&&l>=0) node[++cnt]=Node(l,i-1,i-l),l=-1;
if(s[i]=='T'&&l<0) l=i;
}
if(l>=0) node[++cnt]=Node(l,n-1,n-l);
if(cnt==0) {
printf("0\n");
continue;
}
sort(node+1,node+1+cnt);
int ans=node[1].mm;
for(int i=1;i<=cnt&&node[i].mm>=ans-1;i++) {
if(GO(node[i].l-1,1)) node[i].mm++;
if(GO(node[i].r+1,2)) node[i].mm++;
ans=max(ans,node[i].mm);
}
printf("%d\n",ans);
}
return 0;
}
为什么辣么简单的暴力题要切两个半小时呢？因为我一直往 DP 和暴搜上考虑，浪费了两个小时。警钟长鸣。