题解

看到这种每次能 *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$ 所需的最小操作次数。

题目描述

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

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