题解

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

题目描述

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

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

第一行输入一个整数 $n$ （ $1 \leq n \leq 20000$ ）。第二行输入 $n$ 个整数表示序列 $a$ （ $1 \leq a_i \leq 20000$ ）。

输出一行一个整数表示答案。

5
10 10 5 6 4

对于序列 $[10, 10, 5, 6, 4]$ ，我们可以进行以下操作：

最终序列为 $[5, 5, 5, 6, 8]$ ，共进行了 3 次操作。

8
10 3 1 6 8 12 7 5