B3636 文字工作 題解

· · 题解

B3636 文字工作 題解

管理员注：

阅读本文章前，请先阅读 \ \texttt{ShanCreeper} B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

给定 n，从 1 开始每次可以将这个数字翻倍或加 1，问最少几次能达到 n。

可以用 dp。

继续设计 f(n)，已知 f(1)=0。

所以：

f(n)=\min \left\{\begin{array}{l} f(n-1)+1 \\ f(\frac{n}{2})+1 \end{array}\right.

并且显而易见，当前字数若为奇数个时，不可能为翻倍而来。