Zach(1) 刷屏问题

我们经常想刷屏，比如打100个“顶” like this

LZ威武啊！
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶

我们一般是先打几个顶，然后复制粘贴若干次。

那么，连续输入n个“顶”最少需要多少次按键呢？连续输入至少n个“顶”，最少需要多少次按键呢？

注：输入一个“顶”视为一次按键，复制一次视为一次按键，粘贴一次视为一次按键。

ctrl + A doesn't count as a key stroke?

does it have to be exactly 100, or > 100 is also ok?

does it have to be exactly 100, or > 100 is also ok?

int getMin(n)
{
    if(n <= 4)
        return n;
    return getMin(floor(sqrt(n))) + getMin(n - floor(sqrt(n)) * floor(sqrt(n)));
}
不知道对不对

回复 5# Imbalism
为什么min和max都只有一个实参？

另外说说我的想法，严格等于n的情况用n^2的dp应该能出来，不知道能不能更好。至少n的情况，递推一下i次操作所能产生的最大数目就行，考虑到这个基本是指数增长的，可以认为logn就能出来

   

想用i次操作弄出尽可能多的“顶”，策略是先直接输入几次，i为奇数则先输入3次，i为偶数则先输入两次，然后用剩下的操作不断翻倍。这样如果能把公式写出来的话，第二问可能O(1)就能出来。当然必须把取log的代价看做常数

1. ctrl + A doesn't count as a key stroke?
2. does it have to be exactly 100, or > 100 is also ok?
小K 发表于 2011-4-20 18:00

1. 全选和输入一个字，和复制，和粘贴一样，都算一次
2. 我说了，有两问嘛。
    (1)连续输入n个“顶”最少需要多少次按键呢？
    (2)连续输入至少n个“顶”，最少需要多少次按键呢？

回复  Imbalism
为什么min和max都只有一个实参？

另外说说我的想法，严格等于n的情况用n^2的dp应该能出 ...
darksteel 发表于 2011-4-20 18:36

Yep. I guess it's a typical DP problem

回复 9# zach
但我刚才又想了下，似乎可以复制任意长度破坏了这一点。这样除了小于等于4的特殊情况需要处理一下，其它的最后一步肯定由复制得到。如果第二问算出来了，第一问是完全一样的结果，因为完全可以在在最后一次复制的时候少复制一些而得到正好n个。我觉得如果改成每次复制只能翻倍，大概就得用dp了。