题解 P1249 【最大乘积】
【前言】
部分的题解是有一些瑕疵的。
1、贪心法求和sum，扣除sum-n，这种方法当n=8时，就错了。
这种方法的输出是2 3 5 ，但正确答案是3 5 。
2、动态规划通过ln函数，把求积改成求和，非常巧妙。背包是求不超过容积的最多装多少，但这道题是恰好装整个容积。这一点我没有想通。
3、这个题解的方法和已有的一个题解的思路是一致的。
【思路】
1、这道题预先需要知道的一点是：数越多，乘积越大。
“1”对于乘积是没有收益的，我们要从2~n-1中选出尽可能多的数，使它们的和为n。然后把选出的数相乘就是答案。
2、两个特例，“3”和“4”。这两个只能从拆成“1+2”和“1+3”，很多题解里的拆成的是“3”和“4”，哪种对，见仁见智吧。我单点测试了3和4，只能说洛谷的测试点中没有“3”和“4”，无论哪种输出都不会影响AC。
【流程】
输入——选数——高精度乘法——输出。（选数时和高精度乘法无关）
【如何选数】
我们就以13为例，“2”、“3”、“4”都可以选，但是“5”如果选了，sum（2，3，4，5）=14超过13，5不能选。此时sum（2，3，4）=9，还余4，我们把4这个值分配到“2”、“3”、“4”这三个数上。
怎么分最好？这里有两个原则：
（1）增长的数的个数越多，乘积越大。“2+1”、“3+1”、“4+2”优于“2”、“3”、“4+4”；
（2）若只有部分数能增长，那么本身大的增长后，乘积更大。“2”、“3”、“4+1”优于“2+1”、“3”、“4”。
所以对于 “2”、“3”、“4”，余4 来说。
可以都增长，那么变成 “2+1”、“3+1”、“4+1”，余1 。
不能都增长，那么变成 “3”、“4”、“5+1”，余0
vecotr<int>F; //存储可以选择的数，不熟悉vector，开个数组和一个记录数组长度的int len也可以。
void find(){
int sum=0; //已选择的数之和
for(int i=2;i<n;i++){ //遍历所有的数
if(sum+i>n){
int rm=n-sum; //余多少
//把余的值分配给已选的数，从已选的数中，大数开始分配余值，若每个数增长1后，仍有余值，继续从大数开始分配
while(rm){
for(int j=F.size()-1;j>=0&&rm>0;j--){
F[j]++; //已选的数增长1
rm--; //余值减少1
}
}
return ;
}
F.push_back(i);
sum+=i;
}
}【高精度乘法】
选数之后就是把所有选择的数相乘，因为最终值可能很大，所以需要用到高精度乘法，关于高精度乘法，不赘述。
【代码】
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int nA=10005 ;
int n;
vector<int>F; //存储可以选择的数
/*这一部分都是大整数模板代码。*/
struct Bign{
int D[100000];
int len;
Bign(){
fill(D,D+100000,0);
len=0;
}
};
Bign ans;
Bign change(string s){
Bign a;
a.len=s.size();
for(int i=0;i<a.len;i++){
a.D[i]=s[a.len-i-1]-'0';
}
return a;
}
Bign mult(Bign a,int b){
Bign c;
int carry=0;
for(int i=0;i<a.len;i++){
int tmp=a.D[i]*b+carry;
c.D[c.len++]=tmp%10;
carry=tmp/10;
}
while(carry!=0){
c.D[c.len++]=carry%10;
carry/=10;
}
return c;
}
void publish_Bign(Bign a){
for(int i=a.len-1;i>=0;i--){
cout<<a.D[i];
}
}
/*输出*/
void publish(){
for(int i=0;i<F.size();i++){
if(i)cout<<" ";
cout<<F[i];
}
cout<<endl;
publish_Bign(ans);
}
/*高精度乘法，计算所有可以选择的数的乘积*/
void calc(){
ans=change("1");
for(int i=0;i<F.size();i++){
ans=mult(ans,F[i]);
}
}
/*选择和为n尽可能多的数*/
void find(){
int sum=0;
for(int i=2;i<n;i++){
if(sum+i>n){
int rm=n-sum;
while(rm){
for(int j=F.size()-1;j>=0&&rm>0;j--){
F[j]++;
rm--;
}
}
return ;
}
F.push_back(i);
sum+=i;
}
}
/*输入*/
void creat(){
cin>>n;
}
int main(){
creat(); //输入
if(n==3){ //特判“3”
cout<<"1 2"<<endl;
cout<<"2";
}
else if(n==4){ //特判“4”
cout<<"1 3"<<endl;
cout<<"3";
}
else{
find(); //选数
calc(); //相乘
}
publish(); //输出
return 0;
}