一道数字操作题

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

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