题解：P1249 最大乘积

· · 题解

思路

大家看到这题的时候，都想 DFS，结果超时，3 \le n \le 10000。不能暴力，那也只有贪心了。

首先，不可能将 n 分解出 1，因为 1 和任何数乘，结果没变。这样会浪费 n 的资源，不是最优。

然后特判一下，当 n \le 4 时，自己本身就是最优解。

我们思考一下，如果有两个数的和是 x，那么这两个数的积最大是多少？很明显，这两个数的差尽量小，也就是尽量连在一起。设 x=10，那么这两个数最优是 5 和 5，它们的积是 5 \times 5 = 25。

三个数呢？同理，越连续越好。设 n=\sum_{i=1}^{k} a_i，使 \prod_{j=1}^{k} a_j 最大，则尽量满足 \lvert a_1-a_2 \rvert=0,\lvert a_2-a_3 \rvert=0, \cdots ,\lvert a_{k-1}-a_k \rvert=0，也就是我们小学学的“和同近积大”。

知道这个后，对 n 进行分解，从 2 开始。

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int main(){
    int n,sum=0,num=2,p=0;
    cin>>n;
    if(n<=4){
        cout<<n<<endl<<n;
        return 0;
    }
    // 特判 
    while(sum<n){
        if(n-sum<num)
            break;
        a[++p]=num;
        sum=sum+num;
        num++;
        // 分解 
    }
    int s=n-sum;

代码中，s 表示 n 分剩下的数，不能浪费，继续分给 a 数组。按 a 数组中的值从大到小分，这是最优情况。在上面的代码中按 p 从大到小分。

    int tmp=p;
    while(s>0){
        // 将剩下的 s 分配到 a
        a[tmp--]++;
        s--;
        // s 分出一个 1 给 a[tmp] 
        if(tmp==0) tmp=p;
        // 循坏，直到分完 
    }

Subtask #1 没过的看这里，一定要 if(tmp==0) tmp=p;，不然会浪费资源。对于 8 就会浪费。

最后，将 a 数组中所有分解的数乘起来，就是最优答案。

    int ans=1;
    for(int i=1;i<=p;i++){
        cout<<a[i]<<" ";
        ans=ans*a[i];
    }
    cout<<endl<<ans;
    // 乘积 
    return 0;
}

代码打完了，提交上去，20 pts，回来看了看题目，3 \le n \le 10000，那乘积该多大！高精度解决。

代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int b[100001];
string chengfa(string s,string t){
    memset(b,0,sizeof(b));
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    int i,j;
    for(i=0;i<s.size();i++)
        for(j=0;j<t.size();j++)
            b[i+j]+=(s[i]-'0')*(t[j]-'0');
    for(int i=0;i<s.size()+t.size();i++){
        b[i+1]+=b[i]/10;
        b[i]=b[i]%10;
    }
    i=s.size()+t.size();
    while(b[i]==0&&i>0) i--;
    string ans="";
    for(int jj=i;jj>=0;jj--){
        char x=b[jj]+'0';
        ans=ans+x;
    }
    return ans;
}
string c(int x){
    stringstream ss;
    ss<<x;
    string d;
    ss>>d;
    return d;
}
int main(){
    int n,sum=0,num=2,p=0;
    cin>>n;
    if(n<=4){
        cout<<n<<endl<<n;
        return 0;
    }
    // 特判 
    while(sum<n){
        if(n-sum<num)
            break;
        a[++p]=num;
        sum=sum+num;
        num++;
        // 分解 
    }
    int s=n-sum;
    int tmp=p;
    while(s>0){
        // 将剩下的 s 分配到 a
        a[tmp--]++;
        s--;
        // s 分出一个 1 给 a[tmp] 
        if(tmp==0) tmp=p;
        // 循坏，直到分完 
    }
    string ans="1";
    for(int i=1;i<=p;i++){
        cout<<a[i]<<" ";
        ans=chengfa(ans,c(a[i]));
    }
    cout<<endl<<ans;
    // 乘积 
    return 0;
}