题解 CF11E 【Forward, march!】

· · 题解

题目求的是一个分数。那么很自然地想到 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