06
过去的几个月一直在忙于研究生的事务只能现在事后追忆了
| Rank | Author | Solved | Penalty | 1001 28/662 | 1002 34/1357 | 1003 4/20 | 1004 6/25 | 1005 14/403 | 1006 890/3051 | 1007 330/2765 | 1008 209/345 | 1009 448/2271 | 1010 546/1652 | 1011 96/155 | 1012 718/2228 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 300 | team1157 四川大学 | 4 | 15:18:47 | (-3) | 00:48:47 (-2) | 03:42:36 (-4) | 02:35:57 (-1) | 04:51:27 (-3) |
1001 Multiply 2 Divide 2¶
有一个长度为 \(n\) 的序列 \(a\)。
在一次操作中，可以选择一个数 \(a_i\)，将其变为 \(a_i \cdot 2\) 或者 \(\left\lfloor \frac{a_i}{2} \right\rfloor\)。
求将该序列变为一个不下降序列的最小操作次数。
\(1 \le n \le 10^5\)，\(1\le a_i \le 10^5\)。
既然可以对同一个数字多次操作，这些操作的顺序一定是先除后乘。
注意到 \(a_i \le 10^5\)，令 \(m = 10^5\) 为值域上界。
可以有一个简单的 \(dp\)：设 \(f_{i,j,k}\) 表示前 \(i\) 个数不下降，第 \(i\) 个数除了 \(j\) 次后乘了 \(k\) 次的最小操作次数。第二维在 \(\log(m) < 17\)，第三维在 \(200\) 左右，时间复杂度过高。但也就能想到这里了……