每日一题-17th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

LuoGu P1249. 最大乘积

题目描述

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

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

说明

输入格式

只一个正整数 $n$，（$3 \leq n \leq 10000$）。

输出格式

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

第二行是最大的乘积。

样例 1 输入

样例 1 输出

1
2

2 3 5
30

思路

这题乍一看好像无从下手，仔细想想好像有迹可循：“将数 $n$ 拆成更大、更多的 ‘和因子’”，这些 “和因子” 的乘积就是最终答案；

一看 $n$ 的范围，最大是 10000，好家伙……再怎么拆，因子乘积的答案用 C++ 内置的所有数据类型都装不下，，所以必然是要 高精度乘法运算 的；这题的难度因为高精度，瞬间就提示了一个档次……

在相乘之前，还要考虑这些 “和因子” 怎么拆。本人想了很长时间都没有办法，只得使用贪心法来碰运气（众所周知，使用没有被证明的贪心法，其正确性是没有保证的）。以下为分析过程：

因为 “一个有限的正数 $n$ 拆成若干互不相等的自然数之和” 的情况一定是有限种，所以在多项式时间内一定能求出最大值（不是 NP 问题，doge）；
考虑拆出来的数里面一定不会有 1。因为如果有 1，那么一定有一个比现在拆分方式的乘积更大的方法（$1\cdot x=x$，所以不如把这个 1 加到其他数上，一定比原来的大）；
这里使用了贪心法作假设：只要拆出来的因数越多，它们的乘积越大。即假设以下命题成立：
$若\space a_i\ge3\space且\sum\limits_{i=1}^ka_i=const\space且\space a_i\ne a_j\space(i\ne j),\space 则\prod\limits_{i=1}^ka_i\space取最大值\Leftrightarrow k\space取最大值$

事实上，在我写完题目才发现上面的命题是成立的，不用假设，可以来一个学过数论的同学证一证 ~
在第2、3思路的基础上，想让乘积最大，必然要让拆分的因子从尽可能小的数开始（不重复）2，3，4，5，……，$x$（1 不在）；所以把 $n$ 分成 $2+3+\cdots+x$ 直至加到大于等于 $n$ ；以下分几种情况：
- 若 $2+3+\cdots+x=n$，那么太棒了，根据假设，这样的拆分就是答案，并且乘积是 $x!$，接下来用高精度运算就行；
  
  那么如果不等的话，会比 $n$ 大多少呢？我们不妨设 $2+3+\cdots+x$ 比 $n$ 大了 $c$；
  
  我们发现， $c$ 一定不会比 $x$ 大，如果是，那么一定会存在序列：$2+3+\cdots+(x-1)\gt n$，这样 $x$ 是不满足定义的；所以 $c\in[1,x]$；
- 若 $c\in[2,x]$，那么 $c$ 一定在这些因子（2~$x$）中，直接剔除它就行了！
- 若 $c=1$，好像在因子里找不到了！怎么办！只能想新的办法：把最小的 2 拆了，一个 1 删掉，另一个补在最大的因子 $x$ 上；
  
  为啥补在最大的数上？事实上这么做是不对的！因为举个例子：$(n-1+1)n\gt(n-1)(n+1)$；
  
  但这道题没事，因为拆分的因子不允许重复！显然有下面的命题成立：
  $a_1\gt a_2\Longrightarrow(a_1+1)a_2\lt a_1(a_2+1)$

这样所有的问题都解决了！虽然我用这种方法（就叫 贪心-累加剔除法 吧）做完了，但是看了看题解，还有同学竟然能用上 01背包算法！

我看了看，他的思路非常巧妙，利用了对数的性质：$ln\space a+ln\space b=ln(ab)$，要求拆分因子的乘积最大，就是求这些拆分因子的对数和最大，问题转化为（n 是输入参数）：

$已知\space a_i\ge3,\space a_i\in\mathbf{N},\space\sum\limits_{i=1}^ka_i=n,\space求\sum\limits_{i=1}^kln\space a_i\space的最大值$

就是经典 01 背包问题！从 $n$ 个自然数中选出 $k$ 个数，使得其对数和最大：$n$ 个物品（每一类仅有一个）、背包体积为 $n$、每个物品体积 $C_i=i$、每个物品价值 $W_i=ln\space i$（$i\in[1,k]$）；

另外背包一定能恰好装满：因为这里 $\sum\limits_{i=1}^ka_i=n$；

下面将这两个方法都实现一遍；

实现

先实现模拟高精度类（不需要的功能可以自己删掉，这里为了未来的重用性功能写的丰富些，比如这道题只用到了 构造函数、赋值运算符重载函数 和 LongLongInt operator*(const LongLongInt& a, const LongLongInt& b) 这三个函数）：

#ifndef _self_uInt_3248_h
#define _self_uInt_3248_h
#include <iostream>
using namespace std;

class LongLongInt {
    friend ostream& operator<<(ostream& os, const LongLongInt& i);
    friend istream& operator>>(istream& is, LongLongInt& i);
    friend LongLongInt operator+(const LongLongInt& a, const LongLongInt& b);
    friend LongLongInt operator*(const LongLongInt& a, const LongLongInt& b);
    friend bool operator==(const LongLongInt& iL1, const LongLongInt& iL2);
private:
    char* ch;
    int length;
    static constexpr int MaxLength = 10000;
    char* LongLong2String(long long i, int &len) const;
    LongLongInt digitMulti(int digit) const;
public:
    LongLongInt();
    LongLongInt(const long long& iL);
    LongLongInt(const LongLongInt& num);
    LongLongInt(LongLongInt&& tempIL);
    ~LongLongInt();
    LongLongInt& operator=(const LongLongInt& iL);
    LongLongInt& operator=(LongLongInt&& tempIL);
    LongLongInt operator<<(const int& moveDigit) const;
    LongLongInt operator>>(const int& moveDigit) const;
    LongLongInt factorial();
};

#endif // !_self_uInt_3248_h

#include "self_uInt_3248.h"
#include <iostream>
#include <cstring>
using namespace std;

// Constructors & Destructors----------------------------------

LongLongInt::LongLongInt() { ch = new char[MaxLength] {'0'}; length = 1; }

LongLongInt::LongLongInt(const long long& iL) { ch = LongLong2String(iL, length); }

LongLongInt::LongLongInt(const LongLongInt& num) {
    ch = new char[num.length + 1] {0};
    for (int i = 0; i < num.length; ++i) ch[i] = num.ch[i];
    ch[num.length] = '\0';
    length = num.length;
}

LongLongInt::LongLongInt(LongLongInt&& tempIL) {
    ch = tempIL.ch; length = tempIL.length;
    tempIL.ch = nullptr;
}

LongLongInt::~LongLongInt() { if (ch) delete ch; }

//-------------------------------------------------

// Tool functions -----------------------------------
char* LongLongInt::LongLong2String(long long i, int& len) const {
    if (!i) { char* c = new char[2] {'0', '\0'}; len = 1; return c; }
    unsigned long long mag = 1;
    int digitNum = 0;
    for (; i / mag; mag *= 10, ++digitNum); mag /= 10;
    len = digitNum;
    char* invStr = new char[digitNum + 1] {0};
    for (; digitNum; mag /= 10, --digitNum) {
        invStr[digitNum - 1] = i % (mag * 10) / mag + '0';
    }
    invStr[len] = '\0';
    return invStr;
}

LongLongInt LongLongInt::digitMulti(int digit) const {
    LongLongInt ans;
    int preOut = 0, out = 0;
    for (int i = 0; i < length; ++i) {
        int temp = (ch[i] - '0') * digit + preOut;
        if (temp >= 10) { out = temp / 10; temp -= out * 10; }
        ans.ch[i] = temp + '0';
        preOut = out; out = 0;
    }
    ans.length = length;
    if (preOut) { ans.ch[length] = preOut + '0'; ans.ch[length + 1] = '\0'; ++ans.length; }
    else ans.ch[length] = '\0';
    return ans;
}

//-------------------------------------------------

// overload functions ---------------------------------

LongLongInt& LongLongInt::operator=(const LongLongInt& iL) {
    if (&iL == this) return *this;

    if (ch) delete ch;
    ch = new char[iL.length + 1] {0};
    length = iL.length;
    for (int i = 0; i < iL.length; ++i) ch[i] = iL.ch[i];
    ch[length] = '\0';
    return *this;
}

LongLongInt& LongLongInt::operator=(LongLongInt&& tempIL) {
    if (&tempIL == this) return *this;

    if (ch) delete ch;
    ch = tempIL.ch; length = tempIL.length;
    tempIL.ch = nullptr;
    return *this;
}

bool operator==(const LongLongInt& iL1, const LongLongInt& iL2) {
    return !strcmp(iL1.ch, iL2.ch);
}

istream& operator>>(istream& is, LongLongInt& iL) {
    if (iL.ch) delete iL.ch;
    char* temp = new char[iL.MaxLength] {0};
    is >> temp; int len = strlen(temp);
    iL.ch = new char[len + 1] {0};
    for (int i = 0; i < len; ++i) iL.ch[i] = temp[len - i - 1];
    iL.ch[len] = '\0'; iL.length = len;
    return is;
}

ostream& operator<<(ostream& os, const LongLongInt& iL) {
    for (int i = iL.length - 1; i >= 0 && iL.ch[i]; --i) os << iL.ch[i];
    return os;
}

LongLongInt operator+(const LongLongInt& a, const LongLongInt& b) {
    const LongLongInt& maxLenNum = (a.length >= b.length ? a : b),
        & minLenNum = (a.length < b.length ? a : b);
    LongLongInt ans; ans.length = maxLenNum.length;
    bool preOut = 0, out = 0, minEnd = 0;
    int indexOfMax = 0, indexOfMin = 0;
    for (; indexOfMax < maxLenNum.length; ++indexOfMax) {
        int temp = minLenNum.ch[indexOfMin] - (minEnd ? '\0' : '0') + maxLenNum.ch[indexOfMax] - '0' + preOut;
        if (temp >= 10) { temp -= 10; out = 1; }
        ans.ch[indexOfMax] = temp + '0';
        preOut = out; out = 0;
        if (indexOfMin < minLenNum.length) { ++indexOfMin; if (indexOfMin > minLenNum.length - 1) minEnd = 1; }
    }
    if (preOut) { ans.ch[indexOfMax] = '1'; ++ans.length; ++indexOfMax; }
    ans.ch[indexOfMax] = '\0';
    return ans;
}

LongLongInt operator*(const LongLongInt& a, const LongLongInt& b) {
    LongLongInt ans; 
    if (a == 0 || b == 0) return ans;
    for (int i = 0; i < b.length; ++i) {
        LongLongInt temp = a.digitMulti(b.ch[i] - '0');
        ans = ans + (temp << i);
    }
    return ans;
}

LongLongInt LongLongInt::operator<<(const int& moveDigit) const {
    if (length == 1 && ch[0] == '0' || !moveDigit) return *this;
    LongLongInt ans;
    char* newCh = new char[length + moveDigit + 1] {0};
    for (int i = 0; i < moveDigit; ++i) newCh[i] = '0';
    for (int i = moveDigit; i < length + moveDigit; ++i) 
        newCh[i] = ch[i - moveDigit];
    newCh[length + moveDigit] = '\0';
    ans.ch = newCh; ans.length = length + moveDigit;
    return ans;
}

LongLongInt LongLongInt::operator>>(const int& moveDigit) const {
    char* newCh; LongLongInt ans;
    if (moveDigit >= length) { newCh = new char[2] {'0', '\0'}; ans.length = 1; }
    else {
        newCh = new char[length - moveDigit + 1] {0};
        for (int i = 0; i < length - moveDigit; ++i) newCh[i] = ch[i + moveDigit];
        newCh[length - moveDigit] = '\0'; ans.length = length - moveDigit;
    }
    ans.ch = newCh;
    return ans;
}

//------------------------------------------------

// Special needs: factorial
LongLongInt LongLongInt::factorial() {
    if (*this == 0) return (*this) + LongLongInt(1);
    else if (*this == 1 || *this == 2) return *this;
    LongLongInt ans = 2;
    for (LongLongInt iL = 3;; iL = iL + 1) {
        if (iL == *this) { ans = ans * iL; break; }
        ans = ans * iL;
    }
    return ans;
}

以上的类在提交代码时可以粘到一个文件中；

方法 1（贪心-累加剔除法）：

#include "self_uInt_3248.h"
using namespace std;

int main() {
    int n, tmp = 0, maxFactor; cin >> n;
    for (maxFactor = 2; tmp < n; ++maxFactor) tmp += maxFactor;
    --maxFactor;
    if (tmp == n) {
        for (int i = 2; i <= maxFactor; ++i) cout << i << ' ';
        cout << endl << LongLongInt(maxFactor).factorial();
    }
    else {
        int redundant = tmp - n; LongLongInt ans(1);
        if (redundant == 1) {
            for (int x = 3; x < maxFactor; ++x) {
                cout << x << ' ';
                ans = ans * LongLongInt(x);
            }
            cout << maxFactor + 1 << ' ';
            ans = ans * LongLongInt(maxFactor + 1);
        }
        else {
            for (int x = 2; x <= maxFactor; ++x) {
                if (x == redundant) continue;
                cout << x << ' ';
                ans = ans * LongLongInt(x);
            } 
        }
        cout << endl << ans;
    }
    return 0;
}

方法 2（动态规划-01背包法）：

#include "self_uInt_3248.h"
#define INF 2147483647
using namespace std;

void pack01(int itemNum, int capacity, int* costs, double* values, double* maxValue, bool* select) {
    double accept, reject;
    // 要求恰好填满的背包，初始化为 -INF
    for (int v = 0; v <= capacity; ++v) maxValue[v] = -INF;
    for (int i = 1; i <= itemNum; ++i) {
        for (int v = capacity; v >= costs[i]; --v) {
            reject = maxValue[v], accept = maxValue[v - costs[i]] + values[i];
            select[v] = reject < accept;
            maxValue[v] = reject > accept ? reject : accept;
        }
    }
}

int main() {
    int n; cin >> n;
    int* costs = new int[n + 1] {0};
    double* values = new double[n + 1] {0};
    double* mValue = new double[n + 1] {0};
    bool* select = new bool[n + 1] {0};
    for (int i = 1; i <= n; ++i) {
        costs[i] = i; values[i] = log(i);
    }
    pack01(n, n, costs, values, mValue, select);
    
    LongLongInt ans(1);
    for (int i = 1; i <= n; ++i) {
        if (select[i]) {
            cout << select[i] << ' ';
            ans = ans * LongLongInt(i);
        }
    }
    cout << endl << ans;
    return 0;
}