[數論]OI練習題：最優分解方案 best 解題報告

[問題描述]

經過第一輪的遊戲，不少同學將會獲得聖誕特別禮物，但這時細心的數學課代表發現了一個問題：留下來的人太多而使禮物數量可能不夠，為此，加試了一道數學題：將一個正整數 n 分解成若干個互不相等的正整數的和，使得這些數的乘積最大，當主持人報出一個 n 後，請你立即將這個最大值報出來，現請你幫你的好友編一個程序來解決這個問題。

 

[輸入文件]

輸入文件 best.in 中只有 1 個數 n （其中 1<=n<=1000 ）。

[輸出文件]

輸出文件 best.out 中也是一個數，是乘積的最大值。

[輸入樣例]

7

[輸出樣例]

12

【分析】

 如果分解為可以是相等的自然數的和，那麼分解的答案是m個3和一個2，即最大乘積是3^m*2或者是m個3和一個4，即最大乘積是3^m*4的形式

3*3>2*2*2，最後如果有三個2，要換成兩個3，這樣乘積纔會最大

如 10

    / \

    5 5

 　/\ /\

2 3 2 3

如果把1993分拆成若干個互不相等的自然數的和的分法只有有限種，因而一定存在一種分法，使得這些自然數的乘積最大。

若1作因數，則顯然乘積不會最大。把1993分拆成若干個互不相等的自然數的和，因數個數越多，乘積越大。為了使因數個數儘可能地多，我們把1993分成2+3…+n直到和大於等於1993。

若和比1993大1，則因數個數至少減少1個，為了使乘積最大，應去掉最小的2，並將最後一個數（最大）加上1。

若和比1993大k（k≠1），則去掉等於k的那個數，便可使乘積最大。

2+3+4+....+62＝1952<1993;

2+3+4+....+63＝2015>1993；

所以n=63。因為2015-1993=22，所以應去掉22，把1993分

（2+3+…+21）+（23+24+…+63）

這樣下來積是最大的

2×3×…×21×23×24×…×63。 

【我的代碼】
裸代碼

C++语言: Codee#25225

001 /*
002 *Prob:最優分解方案 best
003 *Author:Yee-fan Zhu
004 *Website:http://blog.yeefanblog.tk/
005 */
006 #include <cstdio>
007 #include <iostream>
008 #include <cstdlib>
009 #include <cstring>
010 using namespace std;
011
012 const int MAXN=50;
013 int N;
014 int Num[MAXN];
015 int top=0;
016
017 class hugeint
018 {
019 public:
020     int len,num[1000];
021 };
022
023 hugeint Tmp,Ans;
024 hugeint times(hugeint a,hugeint b)
025 {
026     int i,j;
027     hugeint ans;
028     memset(ans.num,0,sizeof(ans.num));
029     for (i=1;i<=a.len;i++)
030         for (j=1;j<=b.len;j++)
031             ans.num[i+j-1]+=a.num[i]*b.num[j];
032     for (i=1;i<=a.len+b.len;i++)
033     {
034         ans.num[i+1]+=ans.num[i]/10;
035         ans.num[i]=ans.num[i]%10;
036     }
037     if (ans.num[a.len+b.len]>0)
038         ans.len=a.len+b.len;
039     else
040         ans.len=a.len+b.len-1;
041     return ans;
042 }
043
044 void work()
045 {
046     scanf("%d\n",&N);
047    
048     if(N==0)
049     {
050         printf("0\n");
051         exit(0);
052     }
053    
054     int Sum=0;
055     int i;
056     for (i=2;;i++)
057     {
058         Sum+=i;
059         if(Sum>N)
060             break;
061     }
062     for (int j=2;j<=i;j++)
063         Num[++top]=j;
064    
065     int tmp=Sum-N;
066     if(tmp==1)
067         Num[1]=0,Num[top]++;
068     else
069         Num[tmp-1]=0;
070 //    printf("%d\n",tmp);
071 }
072
073 void compute()
074 {
075     memset(Ans.num,0,sizeof(Ans.num));
076     Ans.len=1;
077     Ans.num[1]=1;
078    
079     for (int i=1;i<=top;i++)
080     {
081         if(Num[i]==0)
082             continue;
083         int x=Num[i];
084        
085         Tmp.len=0;
086         memset(Tmp.num,0,sizeof(Tmp.num));
087        
088         while(x)
089         {
090             Tmp.num[++Tmp.len]=x%10;
091             x/=10;
092         }
093        
094         Ans=times(Ans,Tmp);
095     }
096    
097     for (int i=Ans.len;i>=1;i--)
098         printf("%d",Ans.num[i]);
099     printf("\n");
100 }
101
102 int main()
103 {
104     freopen("best.in","r",stdin);
105     freopen("best.out","w",stdout);
106     work();
107     compute();
108     return 0;
109 }