看到这道题，最朴素的想法是用 DFS 求解。

显然这样搜出来的状态数量非常庞大，时间复杂度无法承受，考虑换用 DP 遍历所有状态。

这里有两个方法。

法一：(60pts)

设 $f_i$ 表示正整数 $i(i \in N^+)$ 分解后的最大乘积。

这种情况下乍一看似乎无法转移，因为有后效性，前面的数分解出 $k$ 那么后面就不能分解出 $k$ 了。

既然如此，可以尝试改变状态，多加几维限制。

思考后得出：设 $f(i,j)$ 表示正整数 $i(i \in N^+)$ 分解出的最大整数为 $j$ 时的最大乘积。

初始状态：$\forall i \in [0,n],f(0,i) = 1$

状态转移方程：$f(i,j) = \max\limits_{k=1}^{j - 1} f(i - j,k) \times j$

最终状态 $\max\limits_{i=0}^n f(n,i)$

然而这样是 $O(N^3)$ 的，考虑优化。

令 $s(i,j) = \max\limits_{k=1}^j f(i,k)$

则状态转移方程会变成：$f(i,j) = s(i - j,j - 1) \times j$

初始 $\forall i \in [0,n],s(0,i) = 1$

答案为 $s(n,n)$

这样用 unsigned long long 可以过 $60%$ 的测试数据，但换成高精度则会出现一堆绿色的字母。

（upd:测试时发现，其实根据数学知识，每次转移的 $j$ 并不会太大，有兴趣的可以打个表把 $j$ 的范围缩小些，这样应该能直接 AC）

CODE

法二：

（此方法我暂时给不出严谨的证明，只能感性理解给个大概意思）

再仔细想一想，难道这个 DP 就一定要二维吗？

再想一想，假设我们把 $i$ 分解为 $\{a_1,a_2\ldots a_k \}$，要枚举一个 $a_j(1\le j \le k)$ 进行状态转移。

不难发现，每个数字分别顺序的先后并不影响它对答案的贡献。

换言之，不论枚举的顺序如何，最优状态也一定会被遍历到。

基于此，我们令 $f_i$ 为 $i$ 分解的最优答案，用 bitset 或者 bool 数组记录一下哪些数字被选上了，转移一下就好了。

这个转移方程相当简单，就不写了，详情见 AC 代码。