纪中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)。
输出
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
样例输入
10
样例输出
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)。
输出格式
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
输入输出样例
10
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
………………
于是我们就可以猜着说：
要是不能分成这样子呢？
还是先把它分成这样子，看看剩下来的数字吧
例如：
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
这道题的数据范围也比较小，所以就不需要做那些省时间的高精度操作了