题解

思路

每个位置相互独立。先求从 $1$ 变到每个 $v\le1000$ 所需的最少操作数 $d_v$。当当前值为 $x$ 时，枚举正整数参数后只会得到 $x+\lfloor x/y\rfloor$；按数值递增松弛这些转移即可得到最短步数。

随后每个位置成为一个物品：选择它需要 $d_{b_i}$ 次操作，收益为 $c_i$。总操作数不超过 $k$， 问题变为零一背包。所有 $b_i\le1000$ 的最短步数都很小，因此容量可截断为所有物品代价之和， 也就是至多约 $12n$。

做法

全局预处理 $d_1,\ldots,d_{1000}$。对每组测试把容量设为 $\min(k,12n)$，建立一维背包数组， 依次对每个位置按容量从大到小更新收益，最后输出所有容量状态中的最大值。

正确性证明

预处理枚举了从每个可达值出发的一次合法操作，并按最短路松弛，因此 $d_v$ 等于把单个元素从 $1$ 变为 $v$ 的最少操作数。

若最终获得位置 $i$ 的收益，至少需要 $d_{b_i}$ 次操作；反之，执行对应最短操作序列即可恰好获得它。 不同位置的操作互不影响，所以任意收益方案与一个总代价不超过 $k$ 的物品子集一一对应。 零一背包枚举并比较了全部这样的子集，故其最大值就是原问题最优收益。

复杂度

最短步数预处理规模为常数。每组背包时间复杂度为 $O(n\min(k,12n))$，空间复杂度为 $O(\min(k,12n))$。