CF710E Generate a String 题解

一道比较不错的 DP。

设 \(f_i\) 表示当前字符串长为 \(i\) 时的最小代价，发现这道题麻烦的地方在于 \(f_i\) 可以从 \(f_{i+1}\) 的地方转移过来。

分类讨论一下：

\(i\) 为偶数：

\(i\) 为偶数时 \(f_i\) 能从 \(f_{i-1},f_{\frac{i}{2}},f_{i+1}\) 三个点转移过来，但是 \(f_{i+1}\) 的转移路程是 \(? \to f_{\frac{i+2}{2}} \to f_{i+2} \to f_{i+1} \to f_{i}\)
，总代价是 \(y+2x\)，这显然不如 \(? \to f_{\frac{i+2}{2}} \to f_{\frac{i}{2}} \to f_{i}\) 更优，总代价是 \(y+x\)。

所以 \(i\) 为偶数的转移方程是 \(f_{i}=\min\{f_{i-1}+x,f_{\frac{i}{2}}+y\}\)。

\(i\) 为奇数：

\(i\) 为奇数时 \(f_i\) 能从 \(f_{i-1},f_{i+1}\) 转移过来，接下来讨论 \(f_{i+1}\) 的转移思路。

显然 \(f_{i+1}\) 不能从 \(f_{i}\) 转移，于是只能从 \(f_{i+2},f_{\frac{i+1}{2}}\) 转移，发现 \(f_{i+2}\) 又是个奇数，因此如果从 \(f_{i+2}\) 转移的话路径只能是这样：

\(? \to f_{\frac{i+1}{2}} \to f_{\frac{i+3}{2}} \to f_{i+3} \to f_{i+2} \to f_{i+1} \to f_{i}\)

总代价是 \(4x+y\)，显然不如从 \(f_{i+1}\) 的转移路径 \(? \to f_{\frac{i+1}{2}} \to f_{i+1} \to f_{i}\)，总代价是 \(y+x\)。

所以 \(i\) 为奇数的转移方程是 \(f_{i}=\min\{f_{i-1}+x,f_{\frac{i+1}{2}}+x+y\}\)。

所以最后的方程就是上面两个式子综合一下就好了。

Code：GitHub CodeBase-of-Plozia CF710E Generate a String.cpp