CF1845E Boxes and Balls 笔记

由贪心，对于一个 $a\to a^{\prime }$，他所耗费的步数是可以贪心求出的：即若 $\sum a_i^{\prime }>\sum a_i$，$a_i$ 不断往左移；否则往右移。并且在最优步数 $s$ 往后想刷步数达到 $k$ 步则只能选择一个球左右横跳，即 $s\equiv k(\mathrm{mod}2)$。

因此可以设 $f_{i,j,s}$ 表示考虑 $a^{\prime }$ 前 $i$ 个位置，放了 $j$ 个球，总共耗费了 $s$ 步，假设 $a$ 中第 $j$ 个球位于 $a_x$，则有

$$f_{i,j,s}\leftarrow f_{i-1,j-1,s-|a_x-i|}$$

时空复杂度均为 $O(n^3)$。

考虑优化状态拆贡献，对于位置 $i$ 来说，在这个位置的操作次数就是 $g_i=|\sum a_i-a_i^{\prime }|$，并且相邻两个位置的贡献相差不会超过 $1$，由 $\sum g_i\le k$，易得 $g$ 的量级是 $\sqrt{k}$ 的。

设 $f_{i,j,k}$ 表示考虑前 $i$ 个位置，$g_i=j$，$\sum g_i=k$ 的方案数，枚举 $a^{\prime }$ 这个位置放不放球

$$f_{i,j,k}\leftarrow \sum _{a_i^{\prime }=0/1}{f}_{i-1,j-a_i^{\prime }+a_i,k-|j-a_i^{\prime }+a_i|}$$

时间复杂度 $O(nk\sqrt{k})$，空间复杂度可用滚动数组优化到 $O(k\sqrt{k})$。