CF1845E
这种 \(01\) 串的描述方式一般是提出 \(1\) 的位置去讨论，设原串 \(1\) 出现位置是 \(p_1,...,p_m\).
考虑最后生成的串的性质，描述其 \(1\) 的位置，\(q_1,...q_m\)。
那么至少移动步数为 \(\sum |p_i-q_i|\)，因为 \(1\) 的位置是相对不变的。
考虑一个一个 \(1\) 往里填，设 \(f_{i,j,k}\) 表示前 \(i\) 个位置，填入了 \(j\) 个数，\(\sum_{t=1}^j |p_t-q_t|=k\)。
然而这样是 \(n^3\) 的，我们考虑优化状态。
设 \(sum_i\) 表示前 \(i\) 个数有多少个 \(1\)。
如果当前填到第 \(i\) 个位置，设 \(d=j-sum_i\)，那么就意味着有 \(d\) 个 \(1\) 要挪进来或移出。
然而这样至少移动是 \(d^2\) 的，所以 \(|d|\le \sqrt k\)。
那么将 \(f_{i,j,k}\) 定义改为填入了 \(sum_i+j\) 个数，且 \(|j|\le \sqrt k\)。
复杂度是 \(nk^{1.5}\)。
CF1859E
这个题有一个肉眼可见的 dp，设 \(f_{i,j}\) 表示处理到前 \(i\) 个数组成了区间，当前区间长度是 \(j\) 的最大值。
然而转移是 \(O(n)\) 的，所以总共的复杂度是 \(O(n^3)\).
考虑寻找性质。发现可以利用绝对值的性质，由于 \(x\le |x|\)，所以我们可以直接把绝对值拆开。
题目要求最大值。两个绝对值直接拆成四个方面，总会遇到最大值。
\(f_{i,j}\) 的转移可以从 \(i'-j'=i-j\) 的转移而来，对于 \(i-j\) 相同的，维护四个方面的最大值。
转移变成 \(O(1)\)，总的复杂度是 \(O(n^2)\)。