纪中23日c组T2 2159. 【2017.7.11普及】max 洛谷P1249 最大乘积

阅读量：5273 次

发布时间：2019-06-14

本文共 3722 字，大约阅读时间需要 12 分钟。

纪中2159. max 洛谷P1249 最大乘积

说明：这两题基本完全相同，故放在一起写题解

纪中2159. max

(File IO): input:max.in output:max.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。

现在你的任务是将指定的正整数n分解成m个(m>=1)互不相同的自然数的和，且使这些自然数的乘积最大。

输入

只一个正整数n，(3≤n≤10000)。

输出

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

样例输入

样例输出

2 3 530

数据范围限制

30%的数据 3<=n<=100

洛谷P1249 最大乘积

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。

现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入格式

只一个正整数n，(3≤n≤10000)。

输出格式

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

输入输出样例

输入 #1复制

输出 #1复制

2 3 530

Solution

考试前，很久、很久、很久之前，我在嵊州与同学一起刷题。随机跳到了这道题，但是都不会。

于是，愉快的放弃了……

于是，今天，我死了。

Algorithm1

尝试用dfs暴力的算。

（对后面的找规律十分重要）

Code1

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
            7 #include
            
              8 #include
             
               9 #include
              
               10 #define IL inline11 #define re register12 using namespace std;13 14 IL int read()15 {16 re int res=0;17 re char ch=getchar();18 while(ch<'0'||ch>'9')19 ch=getchar();20 while(ch>='0'&&ch<='9')21 res=(res<<1)+(res<<3)+(ch^48),ch=getchar();22 return res;23 }24 int n,maxans;25 bool use[10001];26 int q[10001];27 int tail;28 int ans[10001];29 int maxlen;30 IL void dfs(int depth,int sum,int times)31 {32 if(sum==n){33 if(maxans
               
                n) return;42 for(int i=2;i+sum<=n;i++)43 {44 if(!use[i]){45 q[tail++]=i;46 use[i]=1;47 dfs(depth+1,sum+i,times*i);48 q[--tail]=0;49 use[i]=0;50 }51 }52 }53 int main()54 {55 // freopen("max.in","r",stdin);56 // freopen("max.out","w",stdout);57 n=read();58 dfs(0,0,1);59 for(int i=0;i

Code1

n=22 2n=33 3n=44 4n=52 3 6n=62 4 8n=73 4 12n=83 5 15n=92 3 4 24n=102 3 5 30n=112 4 5 40n=123 4 5 60n=133 4 6 72n=142 3 4 5 120n=152 3 4 6 144n=162 3 5 6 180n=172 4 5 6 240n=183 4 5 6 360n=193 4 5 7 420n=202 3 4 5 6 720n=212 3 4 5 7 840n=222 3 4 6 7 1008n=232 3 5 6 7 1260n=242 4 5 6 7 1680n=253 4 5 6 7 2520n=263 4 5 6 8 2880n=272 3 4 5 6 7 5040n=282 3 4 5 6 8 5760n=292 3 4 5 7 8 6720n=302 3 4 6 7 8 8064n=312 3 5 6 7 8 10080n=322 4 5 6 7 8 13440n=333 4 5 6 7 8 20160n=343 4 5 6 7 9 22680n=352 3 4 5 6 7 8 40320n=362 3 4 5 6 7 9 45360n=372 3 4 5 6 8 9 51840n=382 3 4 5 7 8 9 60480n=392 3 4 6 7 8 9 72576n=402 3 5 6 7 8 9 90720

table

Algorithm2

尝试找规律

首先，1肯定是不能取的（1本身除外）（这不是废话吗？占总和又不算乘积的说……）

有一些特别的数，比如5,

它与比它小的数字不一样：

5被分成了2，3

但是比5小的数只被分成了一个数

像这样的数，还有很多，比如：

9：2，3，4

14：2，3，4，5

20：2，3，4，5，6

………………

于是我们就可以猜着说：

如果一个数可以被分成从2开始的连续的一串数字之和

那么这些数字就是这个数的“最大乘积”。

要是不能分成这样子呢？

还是先把它分成这样子，看看剩下来的数字吧

例如：

5被分成2,3

6不能正好分成从2开始连续的数字串

但是它被分成了2,3+1

7则被分成了2+1,3+1

8则被分成了2+1,3+2

9可以正好分成从2开始连续的数字串

……………………

那不就先减，减到不能减，再将2,3,4,5,6……这个数字串从右到左，再从右到左反复+1嘛！

（+1的过程也可以用除法和余数实现）

最后求乘积可是要用高精度的呦！

Code2

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
           7 #include
           
             8 #include
            
              9 #include
             
              10 #define IL inline11 #define re register12 using namespace std;13 int n;14 int arr[10000];15 int a[10000];16 int main()17 {18 // freopen("max.in","r",stdin);19 // freopen("max.out","w",stdout);20 cin>>n;21 int i=2;22 while(n-i>=0) n-=i++;i--;23 for(int j=2;j<=i;j++)24 arr[j]=j;25 if(n)//现在有i-1个数 26 {27 int j;28 for(j=2;j<=i;j++) arr[j]+=n/(i-1);29 for(j=i;j>=i+1-n%(i-1);j--) arr[j]++;30 }31 for(int j=2;j<=i;j++) cout<
              
               <<" ";32 a[0]=1;33 for(int j=2;j<=i;j++)34 {35 for(int k=0;k<10000;k++)36 {37 a[k]*=arr[j];38 }39 for(int k=0;k<10000;k++)40 {41 a[k+1]+=a[k]/10;42 a[k]%=10;43 }44 }45 cout<
               
                =0;j--)48 {49 if(a[j]) flag=1;50 if(flag) cout<