转载

c++聪聪看书（满分代码）

聪聪是一个善良可爱、睿智聪慧的好孩子。聪聪喜欢看书，这一天她在看一本书时看到

了这样一个问题：给你一个正整数n，你要将它分成若干个自然数Ai的和的形式，并且使得

这若干个自然数Ai的乘积尽量大，并输出最大乘积。比如n=5的情况，最优的方案是5=2+3，

答案为6。这么简单的问题聪聪当然会做了，她想考考你，你能不能比她先给出问题的答案

呢？

【输入】

输入文件名为reading.in 共1行，包含1个正整数n。

【输出】

输出文件reading.out 共1行，包含1个整数，表示最大乘积。

【输入输出样例】

reading.in/reading.out

【数据范围】
对于30%的数据，1≤n≤10。
对于60%的数据，1≤n≤100。
对于100%的数据，1≤n≤10000。

原文地址：http://www.cnblogs.com/scx2015noip-as-php/p/ccks.html

思路在上面那个之前的贴子网址说过了，上次我们遗留下一个问题，就是n=10000时，结果太大，所以我们要高精度。所以现在不多说，上高精度代码，核心代码和上次60分算法一样，剩下40分在这次代码里面用高精解决了。

#include<iostream> #include<cstring> using namespace std; void multi(char *a,char *b)//这个函数用来高精度乘法，这里的指针用在函数里代入了数组 {  int x[2001],y[2001];  int s[2001]={0};  int lena=strlen(a),lenb=strlen(b);  int i,j,t;  for(i=0;i<=lena;i++) x[i]=a[lena-i-1]-'0';  for(i=0;i<=lenb;i++) y[i]=b[lenb-i-1]-'0';  for(i=0;i<lena;i++)  {   for(j=0;j<lenb;j++)   {    s[i+j]+=(x[i])*(y[j]);    if(s[i+j]>9)    {     s[i+j+1]+=s[i+j]/10;     s[i+j]%=10;    }   }  }  t=lena+lenb+2;  while(t>0 && s[t]==0) t--;  for(i=t;i>=0;i--) a[t-i]=s[i]+'0'; } int main() {  char a[2001]={0},b[2]={0},c[2]={0};//a数组设置2000位足够  long long n,ans=1;  itoa(3,b,10);//b设为3，在算法方面对a进行乘3工作  cin>>n;  if(n<=4) itoa(n,a,10);//这个if/else可以去了，下面的判断中n<=4时它的结果就自动是n了，不信可以试试  else  {   itoa(ans,a,10);//a设初值1   while(n>4)   {    n-=3;    multi(a,b);   }   if(n!=0){itoa(n,c,10);multi(a,c);}//把n转为字符数组c，然后a和c高精度乘法（等于之前那篇文章的m*n），和之前那篇文章思路等价  }  cout<<a;//a数组不必循环，可直接打出来  return 0; }

正文到此结束