题目大意：给定一个数n，要求将n划分成一些正整数的和，使这些正整数的乘积最大
结论：
如果n是3的倍数 那么将n划分成n/3个3是最优的
如果n是3的倍数+1 那么将n划分成(n-4)/3个3和两个2是最优的
如果n是3的倍数+2 那么将n划分成(n-2)/3个3和1个2是最优的
证明是有的
考虑不是划分成整数，而是划分成任意实数
设我们将n划分成了x个正实数之和
易知当这x个数相等时答案是最优的
那么每个数都是n/x，答案是(n/x)^x
设y=(n/x)^x
则有lny=x[ln(n)-ln(x)]
两侧求导可得y’=(n/x)^x * ( ln(n) – ln(x) – 1 )
当x=n/e时y‘取0 此时乘积最大
因此每个数要尽量靠近e才能使答案最大
现在考虑整数 离e最近的整数是3 因此要把n尽量分成3 不足的用2补齐 这样可以保证是最优的。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 5050using namespace std;struct Int{int xx[M],cnt;Int(int x){xx[cnt=1]=x;}void operator *= (int x){int i;for(i=1;i<=cnt;i++)xx[i]*=x;for(i=1;i<=cnt;i++)xx[i+1]+=xx[i]/10,xx[i]%=10;if(xx[cnt+1]) ++cnt;}}ans(1);int n;int main(){int i;cin>>n;switch(n%3){case 0:for(i=3;i<=n;i+=3)ans*=3;break;case 1:for(i=7;i<=n;i+=3)ans*=3;ans*=4;break;case 2:for(i=5;i<=n;i+=3)ans*=3;ans*=2;break;}cout<<ans.cnt<<endl;for(i=ans.cnt;i&&i>ans.cnt-100;i–)printf("%d",ans.xx[i]);return puts(""),0;}
，你曾经说，等我们老的时候，
