蛋疼研究之怎样刷屏最快？

最近在做网站测试时，遇到了需要在输入框输入 3000 字的测试用例。联想到平时聊天时经常复制粘贴一堆笑脸刷屏讨 MM 欢心的行为，不由想到了一个有趣的问题：为了输入一定数量的字符，最少需要按多少个键？

大家最常用的策略或许是， 先输一些字符，然后全选复制，粘贴到一定规模后，再全选复制，粘贴到一个新的数量级，如此反复。注意到进入全选状态（并且复制后），第一次粘贴将会覆盖掉选中的部分，第二次粘贴才会增加原来的文本长度。当然，全选复制后按一次向右键也可以消除选中状态，不过却并没有节省按键次数。因此我们规定，在输入字符时只有四种原子操作：

1. 按一个按键，输入一个字符

2. 按 Ctrl + A ，全选

3. 按 Ctrl + C ，复制

4. 按 Ctrl + V ，粘贴

排除明显不划算的行为，真正的决策其实只有两种：

1. 按一次按键，输入一个字符

2. 按 k + 2 次按键，将现有内容复制成 k 份。

这样一来，我们就有了一个清晰的递推思路。设 f(n) 表示输入 n 个字符所需要的最少按键次数，则 f(n) 将会在 f(n-1) + 1 和 f(n/k) + k + 2 中取一个最小值（其中 k 取遍 n 的所有约数）。

Mathematica 牛 B 就牛 B 在，这样的动态规划程序只需要一行便能写完：

可见，输入 100 个字符需要 18 次按键。具体方法是，用 5 次按键输入 5 个字符，再用 7 次按键把它变成 25 个字符，再用 6 次按键把它变成 100 个字符。

有趣的是，这个函数并不是单调的。输入 99 个字符需要的按键次数比输入 100 个字符需要的按键次数更多一些，事实上这最少要花费 20 次按键。方法是，先用 5 次按键输入 5 个字符，4 次按键把它变成 10 个字符，单独按一次键添加一个字符， 5 次按键把字符数复制粘贴到 33 ，再来 5 次按键把字符数复制粘贴到 99 。

下面这个图是输入不同的字符数所需要的最少按键。

可以看到， 20 次按键足以应付 100 以内任何数量的字符，也就是说 99 个字符所需要的按键次数已经是 100 个字符以内的情况中最大的了。不过，最悲剧的应该要数 83 个字符了，它是所有至少要用 20 次按键的情况中字符个数最少的（也即首次出现的要用 20 次按键才能输入的情况）。对应的输入方案是 5 → 20 → 80 → 81 → 82 → 83 （直到分析到这里，我才意识到，在考虑输入指定数量的字符时，引入退格键可以带来的更少的按键次数）。

那么， 20 次按键最多可以输入多少个字符呢？为了解决这个问题，我们可以给出另外一个递推式。令 g(n) 为 n 次按键最多可以输入的字符个数。对于每一个 n ，考虑两种转移决策：要么在 n – 1 次按键能够达到的最大字符数基础上加 1 ，要么把 n – k 次按键能够达到的字符数复制成 k – 2 份。也就是说， g(n) 就等于 g(n-1) + 1 和 g(n-k) * (k-2) 的最大值，其中 k 可以从 3 取到 n – 1。我们还是用一句话写下这个转移方程式：

可以看到， 20 次按键足以输入 150 个字符（方案是 6 → 30 → 150 ）， 30 次按键足以输入 1600 个字符（方案是 5 → 25 → 100 → 400 → 1600 ）。这样看上去，我们好像有了快速刷屏的指导思想：粘贴到原来的 4 倍长或者 5 倍长后再进行下一波全选复制粘贴似乎总是最优的选择。另外，这个数列增长得很快， 80 次按键能输入的字符数就已经上亿了。看来，要想刷屏到系统崩溃并不难，不足 100 次按键就能产生上 G 的数据。

似乎这个增长速度是指数级的。描出 g(n) 的图象证实了我们这一想法：

我们自然而然地想到观察数列 g(n) 相邻两项的比值：

容易看到，当 n 到了一定大时，数列已经呈现出了一定的规律，多数时候都是以 1.25 倍的速度增长。给出并证明数列的通项公式或许会是一件非常有趣的事情。