题目描述

塔子哥有一个大小为 $n$ 的序列 $a$，每次操作可以选择序列 $a$ 中的一个数 $x$，把 $x$ 变成 $x \times 2$ 或者 $\left\lfloor \frac{x}{2} \right\rfloor$（对同一个 $x$ 可以操作多次但不能既进行乘操作又进行除操作）。

塔子哥想知道最少需要操作多少次使得序列 $a$ 是不下降的。

题解

看到这种每次能 *2 或 /2 的，操作方案数很多不容易直接做的，就应该往动态规划或者贪心方面去想了。

我们定义 $dp[i][j]$ ，表示对于当前第 $i$ 个数，将其变成 $j$ ，并且保持前 $i$ 数单调不减的最小操作次数。

状态转移：状态可以由 $dp[i - 1]$ 转移过来

• $dp[i][j] = min(dp[i][j], dp[i - 1][k] + cnt)$，其中 $k \le j$ ，$cnt$ 为 $a[i]$ 达到对应的 $j$ 所需的最小操作次数。
• 在转移的时候可以枚举第 $i - 1$ 个数的 $k$ ，对于当前 $a[i]$ 可以用 while 循环维护出到达对应 $j$ 的操作次数。