hiho一下第226周《Ctrl-C Ctrl-V》题目分析

0
0

《Ctrl-C Ctrl-V》题目分析

首先,对于最优方案,Ctrl-A + Ctrl-C + 若干个Ctrl-V一定是连在一起的。

例如 Ctrl-A + A + Ctrl-C + Ctrl-V,一定不如把A放在Ctrl-A之前,即: A + Ctrl-A + Ctrl-C + Ctrl-V

Ctrl-A + Ctrl-C + A + Ctrl-V 一定不如 A + Ctrl-A + Ctrl-C + Ctrl-V。

我们用f[i]表示i个操作最多能输出多少个A。对于最优解,最后一个操作一定是A或者Ctrl-V。

如果最后一个操作是A,则f[i] = f[i-1] + 1;如果最后一个操作是Ctrl-V,我们假设最后一共有连续K个Ctrl-V,则f[i] = f[i-2-K] * (K+1)。

于是我们可以得到一个O(N^2)的DP算法。

当然本题数据范围很大,O(N^2)的DP没办法通过所有的数据。不过我们可以用这个算法得到前若干项的值。例如N=1..25的答案如下:

1 1
2 2
3 3
4 4
5 5
6 6
7 9
8 12
9 16
10 20
11 27
12 36
13 48
14 64
15 81
16 108
17 144
18 192
19 256
20 324
21 432
22 576
23 768
24 1024
25 1296

可以看出,对于N >= 16,f[N] = f[N - 5] * 4。换句话说,当N足够大的时候,最优的策略就是用Ctrl-A + Ctrl-C + Ctrl-V + Ctrl-V + Ctrl-V 5个操作把长度变成4倍。

于是f[N] = f[x] * 4^K, 其中11 <= x <= 15 且 N = x + 5K。其中4^K需要用快速幂实现。

4 answer(s)

0

为什么N=15的时候会是81啊?

  • 喔,弄明白了,一开始直接想着能复制4次就复制四次来着

  • 添加评论
  • reply
2

我没理解错的话,第五行应该是 f[i] = f[i - k -2] * (k + 1), 因为复制还要算上本身。

  • 抱歉,81*3=243

  • 抱歉,我也发现了,丢人。

  • 恩 应该是 * (K+1)

  • 添加评论
  • reply
0

这个题(题意上)其实有点像51nod上的“水群”那题...不过是reverse了的....

0

构造两个矩阵,进行矩阵快速幂

write answer 切换为英文 切换为中文


转发分享