CF1234F 题解

发布时间 2023-12-29 12:40:13作者: liangbowen

blog。小清新题,下文 \(V=20\) 即值域。


反转操作,本质就是选两个不相交连续段拼起来。

显然合法的最终串长度一定 \(\le V\)。将这些合法串预处理出来,那么每个串都对应一个「字母集合」。

随便 DP 一下,求出所有集合中,的最大的合法「字母集合」大小。\(dp_{\small U}\) 就是只选一个连续段的答案(\(U=\small\{\texttt{a},\cdots,\texttt{t}\}\))。

那么选两个连续段就是 \(\max\limits_{s\subseteq U}dp_s+dp_{\small U\normalsize-s}\)。输出即可。

code,时间复杂度 \(O(2^VV)\),其中 \(V=20\)