P**********c
发帖数: 3417 | | d*l
发帖数: 1810 | 2 感觉这个可以在O(1)完成啊
当n比较大的时候，显然是acvvv（5次按键长度*4）的组合对于总体长度增长比较有优势
【在 P**********c 的大作中提到】
: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
: 前面的分析感觉看的七七八八，但是后面的code没看懂。谁来讲一下？尤其是findMaxk部分？
| P**********c
发帖数: 3417 | 3 不对。还有一个输入是'A', 主要就是确定一开始输入几个A. 然后再ctrl+A, ctrl+C, ctr+V
优势
【在 d*l 的大作中提到】
: 感觉这个可以在O(1)完成啊
: 当n比较大的时候，显然是acvvv（5次按键长度*4）的组合对于总体长度增长比较有优势
| i*****e
发帖数: 113 | 4 Be extra cautious for N = 15.
When N = 15, does the sequence { 6A7D } yields the maximum where M = 42?
Imagine if you have a very large number of keystrokes to enter, does
pressing CTRL+V forever gives you the maximum sequence? Remember, you can
redo the entire { CTRL+A, CTRL+C, CTRL+V } operations again and potentially
maximizes the sequence.
For N = 15, the maximum sequence should be:
{ 3A4D4D }, which yields M = 48.
不对。还有一个输入是'A', 主要就是确定一开始输入几个A. 然后再ctrl+A, ctrl+C,
ctr+V
优势
【在 P**********c 的大作中提到】
: 不对。还有一个输入是'A', 主要就是确定一开始输入几个A. 然后再ctrl+A, ctrl+C, ctr+V
:
: 优势
| P**********c
发帖数: 3417 | 5 这些我看懂了，但是不知道后面code怎么找k的，感觉看的很费劲。前面这些解释就分
析了几种情况，没有讲怎么找k.
potentially
,
【在 i*****e 的大作中提到】
: Be extra cautious for N = 15.
: When N = 15, does the sequence { 6A7D } yields the maximum where M = 42?
: Imagine if you have a very large number of keystrokes to enter, does
: pressing CTRL+V forever gives you the maximum sequence? Remember, you can
: redo the entire { CTRL+A, CTRL+C, CTRL+V } operations again and potentially
: maximizes the sequence.
: For N = 15, the maximum sequence should be:
: { 3A4D4D }, which yields M = 48.
:
: 不对。还有一个输入是'A', 主要就是确定一开始输入几个A. 然后再ctrl+A, ctrl+C,
| d*l
发帖数: 1810 | 6 假设这个输入是m次A + n次ctrl
当n是一个很大的数的时候，可以计算每增加一次按键给长度贡献的倍数：
2d 2^(1/3) = 1.2599
3d 3^(1/4) = 1.3161
4d 4^(1/5) = 1.3195
5d 5^(1/6) = 1.3077
6d -> 2d3d (这里表示6d<=2d3d，如果出现n=7的情况，则用2d3d来填充，下同)
7d -> 3d3d
8d -> 3d4d
9d -> 4d4d
10d-> 4d5d
11d-> 3d3d3d
12d-> 3d3d4d = 5 + 7d
13d-> 3d4d4d = 5 + 8d
14d-> 4d4d4d = 5 + 9d
15d-> 4d5d4d = 5 + 10d = 80
15d-> 3d3d3d3d = 81
16d-> 3d3d3d4d = 5 + 11d
17d-> 3d3d4d4d = 5 + 5 + 7d
从上面可以看出来4d组合中平均每次按键可以让长度*1.3195，是最合适的一个。
所以可以预料当n大于某个特定值的时候，绝大多数是4d的组合。
2d2d<5d 所以2d最多只会出现1次
3d3d3d3d3d<4d4d4d4d 所以3d最多只会出现4次
5d5d<3d3d3d 所以5d最多只会出现1次
6d=2d3d 可以认为6d一次都不会出现
7d及以上都不会存在。
3d5d<4d4d 所以3d和5d不会共存
2d5d<3d4d 所以2d和5d不会共存
2d4d<3d3d 所以2d和4d不会共存 (从上面的规律看，当n>7时，不会再出现2d)
4d4d5d<3d3d3d3d 所以5d不会与2个4d共存 (从上面的规律看，当n>11后不会再有5d)
也就是说当n>10以后只有4d和3d的情况
下面按照5的倍数对n (n>11)进行分类，假定下面k是正整数，
n = 5k+12 -> k(4d) + 3d3d3d
n = 5k+13 -> k(4d) + 3d3d4d
n = 5k+14 -> k(4d) + 3d4d4d
n = 5k+15 -> k(4d) + 4d4d4d
n = 5k+16 -> k(4d) + 3d3d3d3d
回来再看本题，给定m+n，其中m为[1,7]内的正整数，求m*f(n)的最大值，相信这已经
可以穷举了。
, ctr+V
【在 P**********c 的大作中提到】
: 不对。还有一个输入是'A', 主要就是确定一开始输入几个A. 然后再ctrl+A, ctrl+C, ctr+V
:
: 优势
|
|
