一道数字操作题

mathe

http://tieba.baidu.com/f?kz=393185659
中，KeyTo9のFans提出了一道复杂的题目:

有9个格子排成一排.

任务开始之前，先在每个格子里写一个非负整数.

然后完成如下任务：

------------------------------------------------------------
最大的数为记为k，把数k从格子中释放出来.

然后你可以进行3次“加1”操作，把(k-1)制造出来并释放.

然后又可以进行3次“加1”操作，把(k-2)制造出来并释放.

……

最后把0释放，任务完成，得分为k.
------------------------------------------------------------

补充说明：

“加1”操作有两种方式，每次操作都只能选择其中一种方式进行：

方式1：直接把某个格子的数加1.

方式2：把一个格子的数修改为另一个格子的数，再把这个格子的数加1.

可以简洁地把两种方式归纳起来表述：

------------------------------------------------------------
把任意一个格子的数改为(x+1).

其中，x必须是修改之前其中一个格子的数.
------------------------------------------------------------

如果你能按照k, k-1, k-2, k-3, ..., 2, 1, 0的顺序把这些数依次制造出来并释放，你就胜利完成任务了.

如果中间有某个数未能制造出来，任务就失败了.

每释放一个数之后，都可以进行不超过3次的“加1”操作.

你需要巧妙地安排好9个格子的初始数字，并巧妙地进行“加1”操作，使得任务能顺利完成，并且得分尽量高.

一个得分为32的示例：

------------------------------------------------------------
9个格子的初始数字为：

32 28 24 20 16 12 8 4 0

释放32之后，第1次“加1”操作把第一个格子改为(28+1)：

29 28 24 20 16 12 8 4 0

再利用第2次和第3次“加1”操作把第一个格子依次改为30、31：

31 28 24 20 16 12 8 4 0

然后释放31，利用2次“加1”操作在第一个格子里制造出30.

30 28 24 20 16 12 8 4 0

然后释放30，只用1次“加1”操作就可以在第一个格子里制造出29.

29 28 24 20 16 12 8 4 0

释放29之后，无须操作，直接释放28.

后面的操作如法炮制，顺利完成任务，得分为32.
------------------------------------------------------------

问：最高得分是多少？如何操作？

如果觉得9个格子没意思，就直接尝试解决这个终极问题吧：

------------------------------------------------------------
格子数为n，用含有n的通项公式表示最高得分.
------------------------------------------------------------


计算机计算结果表明
对于n<=5，这个问题的解分别是
n score  
1　 0  
2　 4  
3　11  
4　24  
5　47
而对于n=6,计算机搜索出85的结果（也就是对于n=6,score>=85;对于n=7,score>=142)
可以注意到前面这么多项如果用多项式拟和，可以写成一个四次多项式，而这个四次多项式,n=6和n=7分别对应值85和144
现在要求证明或否定，这个四次多项式正好是这个所求问题的解。

而推广到更加一般的情况，猜测：如果把每次允许最多三次“加一”操作改为每次最多允许k次“加一”操作，那么得到的分数可以表示成n的k+1次多项式。
比如k=0,很简单，分值是$n-1$
       k=1,也很简单，分值是${(3n+1)n}/2$

gxqcn

看了下原帖，确实比较有趣。
希望在我们这里也有精彩的讨论。

shshsh_0510

很黄很暴力，不知是什么来头

shshsh_0510

感觉应该不会太难吧：
k=3,n很大时：
a1,a2,....an递减排列，则：
a1-a2<=Maxdet1=4
a2-a3<=Maxdetk2=7
a3-a4<=Maxdetk3=13
...

mathe

k=3时非常复杂，倒是k=2时应该还比较容易些，应该可以比较容易得到较大范围n时候的结果。

shshsh_0510

Maxdet1=4,Maxdet2=7,Maxdet3=13....
猜一下：Maxdet(k)=Maxdet(k-1)+3(k-1)

shshsh_0510

一边是消耗，一边是生成，两边正好接上就ok了。

mathe

a2-a3<=Maxdetk2=7
这个就不对,完全可以构造出反例
16 13 3 0=>15 13 4 0=>14 13 6 0=>13 9 6 0=>12 9 6 0=>11 9 6 0=>10 9 6 0=>9 6 3 0=>
...
但是13-3=10>7

shshsh_0510

相关的题目：
有k个数，不限空间，用上述步骤生成 0-n,使k最小。
对相同k共有多少种方案
这些方案生成所需的步数一样吗？什么范围？

shshsh_0510

那是因为进入了“生成”一段的范围