题解 CF11E 【Forward, march!】
YLWang
·
·
题解
题目求的是一个分数。那么很自然地想到 01 规划以后去检验，只要把每一次操作的权值减一个 mid 即可。
考虑 dp。
首先我们预处理一下，把所有不可能的地方的 \texttt{X} 先填上。
我们发现在总的走路串长为奇数的时候处理极其恶心。但考虑到这样一定是相对不优的（一定存在某个位置使得在这个位置放一个 \texttt{X} 就可以让其更优，读者自证不难），就直接忽略即可。
设 f_{i, 0/1} 表示当前匹配到原串的第 i 位，且当前位教官的命令是 \texttt{R/L} 时的最大权值。
第一步转移，即不放 \texttt{X}：
\begin {aligned}
\begin{cases}
f_{i, 0} = max\{f_{i, 0}, f_{i-1, 1} + [s_i = \texttt{R}] - mid\}
\\
f_{i, 1} = max\{f_{i, 1}, f_{i-1, 0} + [s_i = \texttt{L}]-mid\}
\end{cases}
\end {aligned}
第二步转移，即放 \texttt{X}：
容易发现放一个 \texttt{X} 相当于把教官的命令全部左移一格。
\begin {aligned}
\begin{cases}
f_{i, 0} = max\{f_{i, 0}, f_{i, 1} - mid\}
\\
f_{i, 1} = max\{f_{i, 1}, f_{i, 0} -mid\}
\end{cases}
\end {aligned}
边界条件：
\begin {aligned}
\begin{cases}
f_{0, 0} = 0
\\
f_{0, 1} = -mid
\end{cases}
\end {aligned}
最终我们只需要取一手 f_{n, 0} > 0 作为是否成功即可。
要注意的是一些奇奇怪怪的情况。
当 s_0 = s_n = \texttt{R} 的时候，我们不能 naive 地直接加一个 \texttt{X} 到后边去，而应该加在前面。
读者自证不难。
代码链接：https://www.luogu.com.cn/paste/s76jjb3t