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

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

纪中2159. max

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

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

Goto ProblemSet

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如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 5

30

数据范围限制

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 5

30

Solution

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

于是，愉快的放弃了……

于是，今天，我死了。

Algorithm1

尝试用dfs暴力的算。

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

Code1

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #define IL inline

 #define re register

 using namespace std;

 IL int read()

 {

     re int res=;

     re char ch=getchar();

     while(ch<''||ch>'')

         ch=getchar();

     while(ch>=''&&ch<='')

         res=(res<<)+(res<<)+(ch^),ch=getchar();

     return res;

 }

 int n,maxans;

 bool use[];

 int q[];

 int tail;

 int ans[];

 int maxlen;

 IL void dfs(int depth,int sum,int times)

 {

     if(sum==n){

         if(maxans<times){

             memset(ans,,sizeof(ans));

             for(int i=;i<tail;i++) ans[i]=q[i];

             maxlen=tail;

             maxans=times;

         }

         return;

     }

     if(sum>n) return;

     for(int i=;i+sum<=n;i++)

     {

         if(!use[i]){

             q[tail++]=i;

             use[i]=;

             dfs(depth+,sum+i,times*i);

             q[--tail]=;

             use[i]=;

         }

     }

 }

 int main()

 {

 //    freopen("max.in","r",stdin);

 //    freopen("max.out","w",stdout);

     n=read();

     dfs(,,);

     for(int i=;i<maxlen;i++) cout<<ans[i]<<" ";

     cout<<endl<<maxans;

     return ;

 }

Code1

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

n=

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

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #define IL inline

 #define re register

 using namespace std;

 int n;

 int arr[];

 int a[];

 int main()

 {

 //    freopen("max.in","r",stdin);

 //    freopen("max.out","w",stdout);

     cin>>n;

     int i=;

     while(n-i>=) n-=i++;i--;

     for(int j=;j<=i;j++)

         arr[j]=j;

     if(n)//现在有i-1个数

     {

         int j;

         for(j=;j<=i;j++) arr[j]+=n/(i-);

         for(j=i;j>=i+-n%(i-);j--) arr[j]++;

     }

     for(int j=;j<=i;j++) cout<<arr[j]<<" ";

     a[]=;

     for(int j=;j<=i;j++)

     {

         for(int k=;k<;k++)

         {

             a[k]*=arr[j];

         }

         for(int k=;k<;k++)

         {

             a[k+]+=a[k]/;

             a[k]%=;

         }

     }

     cout<<endl;

     bool flag=;

     for(int j=;j>=;j--)

     {

         if(a[j]) flag=;

         if(flag) cout<<a[j];

     }

     return ;

 }

Attention

这道题的数据范围也比较小，所以就不需要做那些省时间的高精度操作了

巴特西

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

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

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

纪中2159. max

题目描述

输入

输出

样例输入

样例输出

数据范围限制

洛谷P1249 最大乘积

题目描述

输入格式

输出格式

输入输出样例

Solution

Algorithm1

Code1

Algorithm2

要是不能分成这样子呢？

Code2

Attention

最新文章

热门文章