转载自http://yjq24.blogbus.com/logs/41658049.html

若干个不同的正整数的和为S,求它们乘积的最大值F(S).

条件中多了“不同的正整数”这个条件，而由调整法我们知道数和数之间越接近越好，那最“相互接近”的当然是一个挨着一个的自然数序列。

和之前类似，分拆中最小的数不可能是1，不妨设S=a[1]+a[2]+…+a[k]，a[1]<a[2]<…<a[k]

1) a[1]>1，反设 a[1]=1，则1*a[k]<1+a[k]

2) a[1]<=3，首先a[1]<=4，否则a[1]>=5时，有a[1]<2(a[1]-2)；而a[1]=4时，实际上F(4)=4时的确a[1]=4，所以我们假定S足够大(S>=6)，则有 4*a[k]<3*(a[k]+1)，故a[1]<=3

根据以上两条知，a[1]=2 or 3.

猜测：a[1]，a[2]，…，a[k] 应为从2或3起始的最多缺一个数的正整数序列。

反证：假设缺两个数，m和n.

若分拆如下：a[1]，…，m-1，m+1，…，n-1，n+1，…，a[k]

则(m-1)(n+1)=mn+m-n-1<mn

实际上由起始条件和序列的“紧凑性”就可以确定下每个数的分拆结果了，整理如下：

情况一：从2开始的连续正整数序列：2，3，4，5，6，…，n

情况二：从2开始的缺一个数的正整数序列：2，3，4，…，m-1，m+1，…，n

情况三：从3开始的连续正整数序列：3，4，5，…，n

情况四：从３开始的缺少一个数的正整数序列，并且该数只能是n：3，4，5，…，n-1，n+1

于是对S，我们找到最小的满足1+2+3+…+n>S的n

若1+2+…+n-S=1，按情况一分拆；

若1+2+…+n-S>=4，按情况二分拆；

若1+2+…+n-S=3，按情况三分拆；

若1+2+..+n-S=2，按情况四分拆。

• Re:一遍AC！爽！附规律如下。 (937) caizhuang0416 2013-10-26 15:27:32