🎈 原创

洛谷 p1249 最大乘积

题目大意

---

将N分解成若干个互不相同数字之和，求乘积的最大值。

思路

---

利用 lna + lnb = ln(a + b)，将乘积的最大值转换为和的最大值。题目就可以化解为，从1, 2, 3…n中选出一些数是他们的和最大。

相当于是一个01背包问题和一个高精度乘法。

题目描述

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

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

输入格式

只一个正整数 nn，（3 \leq n \leq 100003≤n≤10000）。

输出格式

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

第二行是最大的乘积。

输入输出样例

输入 #1

10

输出 #1

2 3 5
30

---

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

struct bigN
{
    int d[10000] = {0};
    int len = 0;
};

bigN multi(bigN a, int b);
void printN(bigN a);
vector<int> ans;

int main(int argc, const char *argv[])
{
    int N;
    cin >> N;
    double W[N + 1], DP[N + 1];
    int flag[N + 1];
    for(int i = 1; i <= N; i++) {
        W[i] = log(i);
        DP[i] = 0;
        flag[i] = 0;
    }
    for(int i = 1; i <= N; i++)
        for(int j = N; j >= i; j--)
            if(DP[j - i] + W[i] > DP[j])
            {
                DP[j] = DP[j - i] + W[i];
                flag[j] = j - i;
            }
    for(int i = N; i; i = flag[i])
        ans.push_back(i - flag[i]);
    bigN a;
    a.len = 1; a.d[0] = 1;
    for(int i = ans.size() - 1; i >= 0; i--)
    {
        cout << ans[i] << (i == 0 ? "\n" : " ");
        a = multi(a, ans[i]);
    }
    printN(a);

    return 0;
}


bigN multi(bigN a, int b)
{
    bigN c;
    int carry = 0;
    for(int i = 0; i < a.len; i++)
    {
        int temp = a.d[i] * b + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    while(carry)
    {
        c.d[c.len++] = carry % 10;
        carry /= 10;
    }
    return c;
}

void printN(bigN a)
{
    for(int i = a.len - 1; i >= 0; i--)
        cout << a.d[i];
}