最速输入问题(上)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

屏幕上有一个字符, 如果只用全选复制粘贴, 要达到$n$个字符最少要多少次按键?

要想达到$N$个字符

  • 如果$N$是个素数,玩完了

只能一个一个复制了, ACVVVVVVVVVV...

也就是 N+2 次.

  • 如果N可以分解

那么我们找出他的一个因子 $\mathrm{i}$ ,另一个因子记为$ \mathrm{ j=N/i}$

也就是达到 $\mathrm{dp[i]}$ 之后粘贴 $j+1$ 次

要不就达到 $\mathrm{dp[j]}$ 之后粘贴$ i+1$ 次

$$\mathtt{dp[i] =Min[dp[j] + i/j + 2, dp[i/j] + j + 2]}$$

我们比较三种路径那个更小就行了.

当然所有路线一起比是一样的...

小tip, 匿函递归, $\mathtt{#0}$表示匿名函数本身.

当然只有复杂度是对数级的时候才可以用, 因为这么写不含记忆化.

当然如果是生成这个序列的话会稍微复杂一些:


如果没有初始输入, 但是允许按键输入会怎么样?

那就把$\mathtt{ dp[i-1]}$也加入比较呗.

$$\mathtt{dp[i] =Min[dp[i-1], dp[j] + i/j + 2, dp[i/j] + j + 2]}$$

就是这样复杂度会从对数增加到线性的不好...


如果允许使用鼠标部分选中会不会得到更好的结果呢?

我们下节再来研究...

发表评论