如何在限定的按鍵次數下輸入最多的字元？

假設：我們有100次按鍵機會， 輸入某個字母（以A為例）消耗一次按鍵機會 ，複製你當前所輸入的所有文字消耗兩次按鍵機會，粘貼你當前所複製的文字消耗一次按鍵機會。那麼如何使用這100次機會，輸入最多的A呢？

---

update:

題目評論中有人提到了M67大大的博文：蛋疼研究之怎樣刷屏最快？

發現數字跟我不一樣，趕緊看了一遍……

其實是在於粘帖的操作到底是怎麼進行的：

M67大大的假定是，粘帖操作第一遍覆蓋了全選的文字，所以粘帖n次就是n倍

我這裡假定的是，粘帖操作是append，所以粘帖n次就是n+1倍

從原理上好像他的做法更對一些……不過我就懶得改了，反正程序里改一丁點就行了。

=============以下為原答案=============

匿名用戶的回答對了一部分：第2個A顯然用按的比複製粘帖要好，所以應該說先按出一串A，然後複製粘帖。

此外，另一個問題是複製粘帖應該粘帖多少次，因為複製一次要2次操作機會，所以可能粘帖多次比只粘帖一次要合算，比如如果你還剩6次操作機會，複製+粘帖+複製+粘帖=4倍，而複製+粘帖+粘帖+粘帖+粘帖=5倍。

所以，上DP……

f = open("dp.txt", "w")
a = [0,1]
b = [0,0]
i = 2
print(0,0,0,file=f)
print(1,1,0,file=f)
while i &<= 100: a.append(0) b.append(0) j = 0 while j &< i: if a[j]+i-j&>=a[i]:
a[i]=a[j]+i-j
b[i]=j
if a[j]*(i-j-1)&>=a[i]:
a[i]=a[j]*(i-j-1)
b[i]=j
j = j + 1
print(i,a[i],b[i],file=f)
i = i+1
f.close()


結果如下：

0 0 0
1 1 0
2 2 1
3 3 2
4 4 3
5 5 4
6 6 5
7 9 3
8 12 4
9 16 4
10 20 5
11 27 7
12 36 8
13 48 9
14 64 9
15 81 11
16 108 12
17 144 13
18 192 14
19 256 14
20 324 16
21 432 17
22 576 18
23 768 19
24 1024 19
25 1296 21
26 1728 22
27 2304 23
28 3072 24
29 4096 24
30 5184 26
31 6912 27
32 9216 28
33 12288 29
34 16384 29
35 20736 31
36 27648 32
37 36864 33
38 49152 34
39 65536 34
40 82944 36
41 110592 37
42 147456 38
43 196608 39
44 262144 39
45 331776 41
46 442368 42
47 589824 43
48 786432 44
49 1048576 44
50 1327104 46
51 1769472 47
52 2359296 48
53 3145728 49
54 4194304 49
55 5308416 51
56 7077888 52
57 9437184 53
58 12582912 54
59 16777216 54
60 21233664 56
61 28311552 57
62 37748736 58
63 50331648 59
64 67108864 59
65 84934656 61
66 113246208 62
67 150994944 63
68 201326592 64
69 268435456 64
70 339738624 66
71 452984832 67
72 603979776 68
73 805306368 69
74 1073741824 69
75 1358954496 71
76 1811939328 72
77 2415919104 73
78 3221225472 74
79 4294967296 74
80 5435817984 76
81 7247757312 77
82 9663676416 78
83 12884901888 79
84 17179869184 79
85 21743271936 81
86 28991029248 82
87 38654705664 83
88 51539607552 84
89 68719476736 84
90 86973087744 86
91 115964116992 87
92 154618822656 88
93 206158430208 89
94 274877906944 89
95 347892350976 91
96 463856467968 92
97 618475290624 93
98 824633720832 94
99 1099511627776 94
100 1391569403904 96


第一個數字表示這是第幾次操作

第二個數字表示最多的A的字元數

第三個數字表示上一步在多少次操作（一步操作定義為按1個A或者複製+粘帖*n次）

比如 7 9 3

表示第7次操作，最多可以輸入9個a字元，上一步在第3次操作。

（注意到3次操作最多輸入3個a字元，此後進行了一次複製+2次粘帖）

我們根據100回溯一下

100 &<-- 96 &<-- 92 &<-- 88 &<-- 84 &<-- 79 &<-- 74 &<-- 69 &<-- 64 &<-- 59 &<-- ... &<-- 19 &<-- 14 &<-- 9 &<-- 4 &<-- 3 &<-- 2 &<-- 1

可以發現在中間有很多步是5次操作（複製+粘帖*3），即翻成4倍，這是為什麼吶？

其實是因為：

當你有20次操作機會時，4^4=256&>243=3^5

當你有30次操作機會時，4^6=4096&>3125=5^5

所以翻成4倍效率最高，但是當只剩不到20次操作機會時，翻3倍反而更好了。

---

from collections import namedtuple
import sys

def aa(n):
dp = [0, 1, 2]
record = namedtuple("record", ["i", "max_char", "prev"])
for i in range(3, n):
plus_one = record(i, dp[i - 1] + 1, i - 1)
back = max([(dp[j] * (i - j - 1), j) for j in range(i - 2)],
key=lambda n: n[0])
copy_paste = record(i, *back)
curr_max = max(plus_one, copy_paste, key=lambda n: n.max_char)
dp.append(curr_max.max_char)
print(curr_max)

if __name__ == "__main__":
aa(int(sys.argv[1]))


LSY-MBP:~ hahaha$ python3 aa.py 101
record(i=3, max_char=3, prev=2)
record(i=4, max_char=4, prev=3)
record(i=5, max_char=5, prev=4)
record(i=6, max_char=6, prev=5)
record(i=7, max_char=9, prev=3)
record(i=8, max_char=12, prev=3)
record(i=9, max_char=16, prev=4)
record(i=10, max_char=20, prev=4)
record(i=11, max_char=27, prev=7)
record(i=12, max_char=36, prev=7)
record(i=13, max_char=48, prev=8)
record(i=14, max_char=64, prev=9)
record(i=15, max_char=81, prev=11)
record(i=16, max_char=108, prev=11)
record(i=17, max_char=144, prev=12)
record(i=18, max_char=192, prev=13)
record(i=19, max_char=256, prev=14)
record(i=20, max_char=324, prev=15)
...
record(i=98, max_char=824633720832, prev=93)
record(i=99, max_char=1099511627776, prev=94)
record(i=100, max_char=1391569403904, prev=95)


感覺每次都要回溯好蠢

---

有人把這個問題推廣了一下寫了篇文章：

Solution Sequences for the Keyboard Problem and its Generalizations

A178715 - OEIS

---

前幾次操作用vim。。強行複製很多遍。。。

---

推薦閱讀：