最速输入问题(上)

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]}$$

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

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

Read More