ARC119F 题解

blog。被自动机做法恶心到了，现在也来恶心一下大家。

\(\color{red}\textbf{以下内容强烈建议自己推一遍，几乎一半是重复的，推完会很爽，并且理解会很深。}\)

\(\color{red}\textbf{以下内容不建议用} \LaTeX\textbf{书写，因为写起来像在吃大便。}\)

暴力 \(dp_{i,a,b}\) 表示当前在 \(i\)，最近的 A/B 在 \(a/b\)，方案数。这个是三次方的。

考虑优化状态：比如说 \(\texttt{BAAAAA...AAB}\) 当前在 B，显然傻逼都知道跳过去最优，那么中间无论有几个 A，state 都是相同的，可以尝试记为同一个 state。

于是直接暴力枚举转移，可以实现一个自动机。

提取大便

开始吃大便！下面标绿的是状态，标红的是当前所在处。

• \(\color{green}\texttt{A}\) 指 \(\texttt{B}\color{red}\texttt{A}\)，意为当前在 A，前一个是 B，后面的不重要。
• \(\color{green}\texttt{B}\) 指 \(\texttt{A}\color{red}\texttt{B}\)。
• \(\color{green}\texttt{AA}\) 指 \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{A}\)。
• \(\color{green}\texttt{BB}\) 指 \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{B}\)。
• \(\color{green}\texttt{AAA}\) 指 \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AA}\)。
• \(\color{green}\texttt{BBB}\) 指 \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BB}\)。
• \(\color{green}\texttt{AAAA}\) 指 \(\color{red}\texttt{B}\color{black}\texttt{AAA..AA}\)。注意即使 \(cnt_A<4\) 但是从 \(\texttt{B}\) 直接跳最优的话，也归属于这个 state。
• \(\color{green}\texttt{BBBB}\) 指 \(\color{red}\texttt{A}\color{black}\texttt{BBB..BB}\)。同上。
• \(\color{green}\texttt{AB}\) 指 \(\texttt{?}\color{red}\texttt{A}\color{black}\texttt{B}\)。
• \(\color{green}\texttt{BA}\) 指 \(\texttt{?}\color{red}\texttt{B}\color{black}\texttt{A}\)。
• \(\color{green}\texttt{@}\) 指 \(\color{red}\texttt{?}\)。注意这里问号的意义是「既可以当作 A 也可以当作 B」。
• \(\color{green}\texttt{@A}\) 指 \(\color{red}\texttt{?}\color{black}\texttt{A}\)。
• \(\color{green}\texttt{@B}\) 指 \(\color{red}\texttt{?}\color{black}\texttt{B}\)。

品尝大便

总计 \(13\) 个状态。转移考虑添加 \(\texttt{A/B}\)，然后尝试用最小代价跑到定义过的状态去。

对于状态 \(\color{green}\texttt{A}\) 与 \(\color{green}\texttt{B}\)，我们有：

• \(\texttt{B}\color{red}\texttt{A}\color{black}\to\texttt{B}\color{red}\texttt{A}\color{black}\texttt{A}\)：不用走即有状态 \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{A}\)，\(\color{green}\texttt{A}\color{black}\xrightarrow{0}\color{green}\texttt{AA}\color{black}\ (\text{add A})\)。
• \(\texttt{B}\color{red}\texttt{A}\color{black}\to\texttt{B}\color{red}\texttt{A}\color{black}\texttt{B}\)：不用走即有状态 \(\color{darkgrey}\texttt{B}\color{red}\texttt{A}\color{black}\texttt{B}\)，\(\color{green}\texttt{A}\color{black}\xrightarrow{0}\color{green}\texttt{AB}\color{black}\ (\text{add B})\)。
• \(\texttt{A}\color{red}\texttt{B}\color{black}\to\texttt{A}\color{red}\texttt{B}\color{black}\texttt{A}\)：不用走即有状态 \(\color{darkgrey}\texttt{A}\color{red}\texttt{B}\color{black}\texttt{A}\)，\(\color{green}\texttt{B}\color{black}\xrightarrow{0}\color{green}\texttt{BA}\color{black}\ (\text{add A})\)。
• \(\texttt{A}\color{red}\texttt{B}\color{black}\to\texttt{A}\color{red}\texttt{B}\color{black}\texttt{B}\)：不用走即有状态 \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{B}\)，\(\color{green}\texttt{B}\color{black}\xrightarrow{0}\color{green}\texttt{BB}\color{black}\ (\text{add B})\)。

对于状态 \(\color{green}\texttt{AA}\) 与 \(\color{green}\texttt{BB}\)，我们有：

• \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{A}\to\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AA}\)：不用走即有状态 \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AA}\)，\(\color{green}\texttt{AA}\color{black}\xrightarrow{0}\color{green}\texttt{AAA}\color{black}\ (\text{add A})\)。
• \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{A}\to\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AB}\)：往后走一步即有状态 \(\color{grey}\texttt{BA}\color{red}\texttt{A}\color{black}\texttt{B}\)，\(\color{green}\texttt{AA}\color{black}\xrightarrow{1}\color{green}\texttt{AB}\color{black}\ (\text{add B})\)。
• \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{B}\to\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BA}\)：往后走一步即有状态 \(\color{grey}\texttt{AB}\color{red}\texttt{B}\color{black}\texttt{A}\)，\(\color{green}\texttt{BB}\color{black}\xrightarrow{1}\color{green}\texttt{BA}\color{black}\ (\text{add A})\)。
• \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{B}\to\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BB}\)：不用走即有状态 \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BB}\)，\(\color{green}\texttt{BB}\color{black}\xrightarrow{0}\color{green}\texttt{BBB}\color{black}\ (\text{add B})\)。

对于状态 \(\color{green}\texttt{AAA}\) 与 \(\color{green}\texttt{BBB}\)，我们有：

• \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AA}\to\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AAA}\)，往前走一步即有状态 \(\color{red}\texttt{B}\color{black}\texttt{AAAA}\)，\(\color{green}\texttt{AAA}\color{black}\xrightarrow{1}\color{green}\texttt{AAAA}\color{black}\ (\text{add A})\)。
• \(\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AA}\to\texttt{B}\color{red}\texttt{A}\color{black}\texttt{AAB}\)，发现走一步啥都到不了，而走两步可以到 \(\color{grey}\texttt{BAA}\color{red}\texttt{A}\color{grey}\texttt{B}\)（往后两步）或 \(\color{grey}\texttt{BAAA}\color{red}\texttt{B}\)（往前一步然后跳过去），此时同时可得两个状态 \(\color{green}\texttt{A}\) 与 \(\color{green}\texttt{B}\)，故 \(\color{green}\texttt{AAA}\color{black}\xrightarrow{2}\color{green}\texttt{@}\color{black}\ (\text{add B})\)。
• \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BB}\to\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BBA}\)，同上，\(\color{green}\texttt{BBB}\color{black}\xrightarrow{2}\color{green}\texttt{@}\color{black}\ (\text{add A})\)。
• \(\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BB}\to\texttt{A}\color{red}\texttt{B}\color{black}\texttt{BBB}\)，往前走一步即有状态 \(\color{red}\texttt{A}\color{black}\texttt{BBBB}\)，\(\color{green}\texttt{BBB}\color{black}\xrightarrow{1}\color{green}\texttt{BBBB}\color{black}\ (\text{add B})\)。

对于状态 \(\color{green}\texttt{AAAA}\) 与 \(\color{green}\texttt{BBBB}\)，我们有：

• \(\color{red}\texttt{B}\color{black}\texttt{AAA..AA}\to\color{red}\texttt{B}\color{black}\texttt{AAA..AAA}\)，不用动即为原状态，\(\color{green}\texttt{AAAA}\color{black}\xrightarrow{0}\color{green}\texttt{AAAA}\color{black}\ (\text{add A})\)。
• \(\color{red}\texttt{B}\color{black}\texttt{AAA..AA}\to\color{red}\texttt{B}\color{black}\texttt{AAA..AAB}\)，跳过大段 \(\texttt{A}\) 即有状态 \(\color{grey}\texttt{BAAA..AA}\color{red}\texttt{B}\)，\(\color{green}\texttt{AAAA}\color{black}\xrightarrow{1}\color{green}\texttt{B}\color{black}\ (\text{add B})\)。
• \(\color{red}\texttt{A}\color{black}\texttt{BBB..BB}\to\color{red}\texttt{A}\color{black}\texttt{BBB..BBA}\)，跳过大段 \(\texttt{B}\) 即有状态 \(\color{grey}\texttt{ABBB..BB}\color{red}\texttt{A}\)，\(\color{green}\texttt{BBBB}\color{black}\xrightarrow{1}\color{green}\texttt{A}\color{black}\ (\text{add A})\)。
• \(\color{red}\texttt{A}\color{black}\texttt{BBB..BB}\to\color{red}\texttt{A}\color{black}\texttt{BBB..BBB}\)，不用动即为原状态，\(\color{green}\texttt{BBBB}\color{black}\xrightarrow{0}\color{green}\texttt{BBBB}\color{black}\ (\text{add B})\)。

对于状态 \(\color{green}\texttt{AB}\) 与 \(\color{green}\texttt{BA}\)，我们有：

• \(\texttt{?}\color{red}\texttt{A}\color{black}\texttt{B}\to\texttt{?}\color{red}\texttt{A}\color{black}\texttt{BA}\)，发现不能不走，而走一步可以到 \(\color{grey}\texttt{?A}\color{red}\texttt{B}\color{grey}\texttt{A}\)（往后一步）或 \(\color{grey}\texttt{?AB}\color{red}\texttt{A}\)（跳过 \(\texttt{B}\)），此时同时可得两个状态 \(\color{green}\texttt{A}\) 与 \(\color{green}\texttt{B}\)，故 \(\color{green}\texttt{AB}\color{black}\xrightarrow{1}\color{green}\texttt{@}\color{black}\ (\text{add A})\)。
• \(\texttt{?}\color{red}\texttt{A}\color{black}\texttt{B}\to\texttt{?}\color{red}\texttt{A}\color{black}\texttt{BB}\)，很明显，无论后续再加 \(\texttt{A/B}\) 都会跳过中间的 \(\texttt{B}\)，故 \(\color{green}\texttt{AB}\color{black}\xrightarrow{0}\color{green}\texttt{BBBB}\color{black}\ (\text{add B})\)。
• \(\texttt{?}\color{red}\texttt{B}\color{black}\texttt{A}\to\texttt{?}\color{red}\texttt{B}\color{black}\texttt{AA}\)，同上，\(\color{green}\texttt{BA}\color{black}\xrightarrow{0}\color{green}\texttt{AAAA}\color{black}\ (\text{add A})\)。
• \(\texttt{?}\color{red}\texttt{B}\color{black}\texttt{A}\to\texttt{?}\color{red}\texttt{B}\color{black}\texttt{AB}\)，同上上上，\(\color{green}\texttt{BA}\color{black}\xrightarrow{1}\color{green}\texttt{@}\color{black}\ (\text{add B})\)。

对于状态 \(\color{green}\texttt{@}\)，我们有：

• \(\color{red}\texttt{?}\color{black}\to\color{red}\texttt{?}\color{black}\texttt{A}\)，不用走即有状态 \(\color{red}\texttt{?}\color{black}\texttt{A}\)，\(\color{green}\texttt{@}\color{black}\xrightarrow{0}\color{green}\texttt{@A}\color{black}\ (\text{add A})\)。
• \(\color{red}\texttt{?}\color{black}\to\color{red}\texttt{?}\color{black}\texttt{B}\)，不用走即有状态 \(\color{red}\texttt{?}\color{black}\texttt{B}\)，\(\color{green}\texttt{@}\color{black}\xrightarrow{0}\color{green}\texttt{@A}\color{black}\ (\text{add B})\)。

对于状态 \(\color{green}\texttt{@A}\) 与 \(\color{green}\texttt{@B}\)，我们有：

• \(\color{red}\texttt{?}\color{black}\texttt{A}\color{black}\to\color{red}\texttt{?}\color{black}\texttt{AA}\)，最优显然是将 \(\texttt{?}\to\texttt{B}\) 然后跳过大段 \(\texttt{A}\)，所以 \(\color{green}\texttt{@A}\color{black}\xrightarrow{0}\color{green}\texttt{AAAA}\color{black}\ (\text{add A})\)。
• \(\color{red}\texttt{?}\color{black}\texttt{A}\color{black}\to\color{red}\texttt{?}\color{black}\texttt{AB}\)，走一步可以到 \(\color{grey}\texttt{A}\color{red}\texttt{A}\color{grey}\texttt{B}\)（将 \(\texttt{?}\to\texttt{A}\) 然后向后走一步）或 \(\color{grey}\texttt{BA}\color{red}\texttt{B}\)（将 \(\texttt{?}\to\texttt{B}\) 然后向后走跳一步），此时同时可得两个状态 \(\color{green}\texttt{A}\) 与 \(\color{green}\texttt{B}\)，所以 \(\color{green}\texttt{@A}\color{black}\xrightarrow{1}\color{green}\texttt{@}\color{black}\ (\text{add B})\)。
• \(\color{red}\texttt{?}\color{black}\texttt{B}\color{black}\to\color{red}\texttt{?}\color{black}\texttt{BA}\)，同上，\(\color{green}\texttt{@B}\color{black}\xrightarrow{1}\color{green}\texttt{@}\color{black}\ (\text{add A})\)。
• \(\color{red}\texttt{?}\color{black}\texttt{B}\color{black}\to\color{red}\texttt{?}\color{black}\texttt{BB}\)，同上上上，\(\color{green}\texttt{@B}\color{black}\xrightarrow{1}\color{green}\texttt{@}\color{black}\ (\text{add B})\)。

走出厕所

最后定义 \(dp_{i,j,s}\) 表示前 \(i\) 个点走了 \(j\) 步，当前所在状态为 \(s\)，方案数。

初始化 \(dp_{0,0,\color{green}\texttt{?}\color{black}}=1\)，跑上述自动机刷表转移即可。

小细节：状态所在的位置不是最终 \(n+1\) 点所在位置，所以还需要记一下 \(dis_s\) 表示状态 \(s\) 还要走多少步到达终点。

具体地，\(dis_{\color{green}\texttt{AA}}=dis_{\color{green}\texttt{BB}}=dis_{\color{green}\texttt{AAA}}=dis_{\color{green}\texttt{BBB}}=2\)，其余均为 \(1\)。判一下统计答案即可。

实现

可以用 map 记录每个状态的 id，这样写转移会清晰很多。

code，时间复杂度 \(O(nk|S|)\)，其中 \(|S|=13\)。