企业官网建设流程全解析

1. 从 1231 这组样例出发：为什么暴力枚举会被卡死

在"信息学奥赛一本通"的动态规划章节里，编号 1275 的【例9.19】乘积最大，是一道被无数人反复讲、又反复讲错的题。它出自早年的 NOIP 提高组，题面朴素得像小学奥数：给一个长度为 N 的数字串，再给 K 个乘号，要求把这 K 个乘号全部插进数字串的缝隙里，使分出来的 K+1 个部分相乘的结果最大。这道题的输入只有两行，输出只有一个整数，看起来五分钟就能写完，但真正动手的人很快会发现两个问题：一是怎么切才最优，靠人眼试根本试不出来；二是当 N 最大到 40 的时候，答案会膨胀到 40 位以上，用long long存结果，直接溢出。

这篇内容我不打算只贴一份代码就完事。和平常写题解不一样，我更想把"为什么状态要这么定义""为什么枚举范围只能这么取""为什么高精度不是可选优化而是必需品"这几件事说透。因为把这道题吃下来，你顺手就能拿下后面一大类区间决策类的问题，投入产出比很高。

1.1 三个容易读漏的题目约束

先把题目条件逐条罗列清楚，这三条里任何一条看漏，代码都过不了。

第一，乘号必须恰好用完。题目说的是"使用 K 个乘号"，不是"至多 K 个"。这意味着分出来的段数固定是 K+1 段，每一段至少得有 1 位数字。这是后面枚举范围推导的直接依据。

第二，数字串的长度 N 可能到 40。数据范围大致是 6 ≤ N ≤ 40，1 ≤ K ≤ 6，且 K < N。40 位数字切 7 段，最后乘积的量级在 10 的 40 次方上下，而long long的极限只有约 9.2 × 10 的 18 次方，连尾数都比不上。所以这道题的正解必须自带高精度。

第三，数字串里可能出现 0。很多人在写状态初值的时候习惯用-1表示"这个状态还没被算过"，结果遇到含 0 的数据就翻车——因为真实的乘积就是 0，跟你用来表示"未计算"的哨兵值撞车了。这个坑我在后面会单独说。

样例输入是4 2加一行1231，样例输出是62。切法是1 * 2 * 31。你可以自己验算一下其他两种切法：1 * 23 * 1 = 23，12 * 3 * 1 = 36，确实都不如 62。

1.2 "让两段尽量匀"的直觉为什么一定会错

大部分人第一次做这道题，脑子里会冒出一个贪心：既然要让乘积最大，那让每一段的数值尽量接近不就行了？这就是小学里"和一定、差越小积越大"的直觉。这个直觉在两个数的场合是对的，但一旦段数变多、而且还要考虑数位长度对数值的影响，它就完全失效了。

举个能直接打脸的例子：数字串1119，K = 1，也就是只切一刀。三种切法分别是 1 × 119 = 119、11 × 19 = 209、111 × 9 = 999。按"尽量匀"的直觉，应该选 11 × 19 = 209，但真实最优是 111 × 9 = 999，差了将近五倍。

为什么会这样？因为在这个数字串里，末位那个 9 是唯一的大数因子，把它单独切出来当乘数，收益远大于让两段位数接近。数字的大小是由高位主导的，而位数接近只是"看起来匀"，跟数值均衡完全是两码事。

更有意思的是，同一组数字串在不同 K 下，最优切点会跳到完全不同的位置。还是1231：K = 1 时最优是12 * 31 = 372（切在中间）；K = 2 时最优却是1 * 2 * 31 = 62（切在靠前的位置）。同一串数字，乘号个数一变，最优结构就变了。这就说明不存在一个固定的贪心规则能覆盖所有情况，必须老老实实做决策搜索。

1.3 枚举所有切法的代价：C(39,6) 不是一个小数字

有人会想，那我把所有切法枚举一遍不就行了？N = 40 的时候，一共有 39 个空隙，从中选 K = 6 个位置放乘号，组合数是 C(39, 6) = 3262623，三百多万种。单看这个数字，好像还在可接受范围内——如果每次切分只需要一次整数乘法的话确实如此。

但问题恰恰在于，每一次切分你都要做 6 次高精度乘法，而每个大数可能有 40 位左右。手写大数乘法是 O(L²) 的，L ≈ 40，一次就是 1600 次基本运算，6 次乘法加起来接近一万次。总运算量大约是 3262623 × 10000 ≈ 3.3 × 10 的 10 次方，这个量级在竞赛的 1 秒时限里是绝对过不去的。

而用动态规划来做，需要执行的乘法次数只有几千次——具体来说，是三层循环枚举状态和决策点的组合数，大概是 K × N² / 2 ≈ 4800 次。从三千万次运算降到五千次，这就是为什么这道题必须用 DP，而不是靠枚举加剪枝硬扛。

2. dp[i][j] 这个状态不是拍脑袋定的

动态规划最难的从来不是写转移方程，而是想清楚状态该怎么定义。很多人背下了这道题的dp[i][j]表示"前 i 个数字里插 j 个乘号"，但问他为什么这么定，答不上来。我把自己当初推导的过程完整复述一遍，希望能帮你建立"状态是被问题结构逼出来的"这种感觉。

2.1 决策动作到底是"选数字"还是"切位置"

很多人一看到"乘积最大"，第一反应是把状态定义成"选到第几个数字为止"，然后纠结于"这个数字到底属于哪一段"。这就是走偏了。

重新读一遍题目：数字串的顺序是不能打乱的，你能做的唯一动作就是在某些缝隙里插入乘号。所以真正意义上的决策，是"第 i 个数字后面到底切不切"。换句话说，问题的解是一组切分位置的集合，而不是一组数字的排列。

一旦意识到决策对象是"切分点"，状态的形状就清晰了：我们需要记录的核心信息是"已经处理到了数字串的第几位"以及"已经用掉了几个乘号"。前者决定了还剩哪些数字可用，后者决定了还剩几个乘号要放。这两个维度合起来，就组成了dp[i][j]。

2.2 为什么按前缀长度的划分天然满足无后效性

动态规划能不能成立，关键看状态转移有没有后效性。所谓无后效性，就是"一旦到达某个状态，未来的决策只跟这个状态本身有关，跟你是怎么走到这里的无关"。

对于这道题，dp[i][j]表示"把前 i 个数字分成 j+1 段的最大乘积"。注意这里的关键点：前 i 个数字被划分成 j+1 段之后，后面剩下的数字串（第 i+1 位到第 N 位）该怎么切，跟前面这 j+1 段具体是怎么分的没有关系。因为你只需要知道前面那部分的最大乘积是多少，后面部分的最优切法不受影响，它们之间唯一的耦合就是"乘起来"这个动作。

这就满足了最优子结构：全局最优解一定能拆成一个前缀最优解乘上一段后缀数字。反过来说，如果你把状态定义成"第 i 个数字所在的段是从第几位开始的"，那状态的维度就爆炸了，而且也不满足无后效性，因为后续切分要依赖的具体分段信息太多了。

2.3 初始化：dp[i][0] 与"无解状态"的处理选择

状态定好之后，边界条件就顺理成章了。

dp[i][0]表示"前 i 个数字里一个乘号都不放"，那就只有一个段，值就是前 i 位数字组成的那个整数。比如样例里的1231，dp[1][0] = 1，dp[2][0] = 12，dp[3][0] = 123，dp[4][0] = 1231。这个初始化用高精度直接对字符串切片转换就行，非常直观。

至于"无解状态"，有两种常见写法。一种是把整个 dp 数组初始化为 0，因为乘积的最小可能值就是 0，0 作为一个合法的"当前最大候选值"不会造成任何错误——任何正数都会把它顶掉，而如果所有候选都算出来是 0，那说明数字串里全是 0，答案本来就是 0。另一种是初始化为 -1 当作哨兵，转移时特判。我强烈建议第一种，理由很实在：这题的乘积天然是非负的，0 本身就是合法值域的下界，用它当初始值既省代码又不会误判，而 -1 哨兵反而会在含 0 的数据上制造歧义。

这里还有个容易忽略的细节：dp[i][j]只对 j < i 有意义。因为要把前 i 个数字切成 j+1 段，每段至少 1 位，所以必须满足 i ≥ j+1。对于 i ≤ j 的状态，我们根本不会去访问，也就不用管。

3. 转移方程里枚举点 t 的上下界，写错一个就 WA

转移方程本身不长，但那个枚举变量的取值范围，是这道题最容易写错的地方。我见过太多人把下界写成 1，结果要么数组越界，要么算出莫名其妙的答案。

3.1 把最后一段单独拎出来

推导转移方程的标准姿势是：思考最后一步做了什么决策。

当我们计算dp[i][j]（前 i 个数字，插 j 个乘号，分成 j+1 段）时，考虑最后一个乘号插在哪里。假设它插在第 t 个数字之后，那么整个串就被切成了两部分：前面是前 t 个数字，后面是从第 t+1 位到第 i 位的这一段。前面那部分需要插 j-1 个乘号，也就是dp[t][j-1]；后面那部分是固定的一个整数，记为num(t+1, i)。

于是转移方程就是：

dp[i][j] = max{ dp[t][j-1] * num(t+1, i) }，对所有合法的 t 取最大值

这里的num(t+1, i)表示数字串从第 t+1 位到第 i 位组成的那个整数。整个思路就是把"最后一段的起点在哪里"枚举一遍，这是所有区间分割类 DP 的通用套路。

3.2 下界为什么是 j 而不是 1

现在来说枚举范围。t 的取值范围必须是[j, i-1]，这两个边界都有明确的现实含义。

先说下界 t ≥ j。因为dp[t][j-1]要求把前 t 个数字分成 j 段（插 j-1 个乘号），而分成 j 段至少需要 j 个数字。如果 t < j，这个状态根本没有意义，强行访问会读到未初始化的垃圾值（在 C++ 里就是默认的 0，会让答案偏小）。这就是为什么下界是 j，而不是想当然的 1。

再说上界 t ≤ i-1。因为最后一段num(t+1, i)至少要包含 1 位数字，所以 t 最多到 i-1。如果写成 t ≤ i，那就切出一段空的，num(i+1, i)在字符串上是个非法区间，转换出来直接错。

顺带说一句，外层循环的顺序必须是先枚举 j，再枚举 i。因为dp[i][j]依赖的是dp[t][j-1]，也就是乘号个数少一层的状态。只有当所有 j-1 层的结果都算完了，才能算第 j 层。

3.3 手推 1231 的完整 DP 表

光看公式还是虚，我们拿样例1231、K = 2 手动跑一遍，把整张表填出来。数字串各位分别是 1、2、3、1。

先算所有区间数值：num(1,1)=1，num(2,2)=2，num(3,3)=3，num(4,4)=1，num(1,2)=12，num(2,3)=23，num(3,4)=31，num(1,3)=123，num(2,4)=231，num(1,4)=1231。

逐格解释一下第 1 层（j = 1）的计算：

• dp[2][1]：t 只能取 1，dp[1][0] * num(2,2) = 1 * 2 = 2。
• dp[3][1]：t 取 1 得1 * num(2,3) = 1 * 23 = 23；t 取 2 得dp[2][0] * num(3,3) = 12 * 3 = 36。取最大值 36。
• dp[4][1]：t 取 1 得1 * 231 = 231；t 取 2 得12 * 31 = 372；t 取 3 得123 * 1 = 123。取最大值 372。

再看第 2 层（j = 2），注意此时 t 的下界是 2：

• dp[3][2]：t 只能取 2，dp[2][1] * num(3,3) = 2 * 3 = 6。
• dp[4][2]：t 取 2 得dp[2][1] * num(3,4) = 2 * 31 = 62；t 取 3 得dp[3][1] * num(4,4) = 36 * 1 = 36。取最大值 62。

最终答案dp[4][2] = 62，跟样例输出完全对上。把这个表亲手推一遍，比看十遍方程都管用——你能亲眼看到 t 的下界是怎么随着 j 往上走的。

4. 40 位数字的乘积有多大：高精度不是可选项

前面提到高精度，这里展开讲清楚：为什么这道题绕不过去，以及手写大数到底要写哪些东西。

4.1 量级估算：为什么 long long 一定会炸

先做一个粗算，让你对答案的大小有个概念。N = 40、K = 6，也就是把 40 位数字切成 7 段。根据"分段越均匀乘积越大"的规律（这个是针对位数成立的经验规律，和前面说的数值均衡不一样），7 段大致是每段 5 到 6 位。

假设数字串里全是 9，40 位切 7 段，比较合理的分法是 6+6+6+6+6+5+5 = 40。每段的数值大概在 10 的 5 次方到 10 的 6 次方之间，7 段乘起来，量级大约是 10 的 40 次方左右。这意味着答案有 40 位左右的十进制数字。

long long能表示的最大值约是 9.22 × 10 的 18 次方，也就是 19 位十进制数。两者差了二十多个数量级，用long long存这个答案，连中间过程都走不完，第一次乘法就会溢出成负数或者垃圾值。

4.2 C++ 手写大数乘法与比较的骨架

C++ 没有任何内置大数，必须手写。好在这道题只需要两个操作：大数乘大数和大数比较大数。我一般用"低位在前"的数组存十进制位，也就是d[0]存个位，d[1]存十位，以此类推。这样进位的时候从下标 0 往大走，写起来最顺手。

大数比较的逻辑很简单：先比位数，位数多的更大；位数相同就从高位往低位逐位比，第一位不同的谁大谁就大。这里有个非常经典的错误，就是只写"位数不同时比位数，位数相同就返回相等"——位数相同但数值不同的情况多了去了，比如 1234 和 4321 都是 4 位，必须逐位比较才能分出大小。

大数乘法的核心是模拟竖式：两层循环把d[i] * d[j]累加到结果的第i+j位上，等所有位都累加完，再从低位到高位统一处理进位。中间累加用的数组要开得足够大，长度份应该是两个乘数位数之和再加 2。

关于中间值会不会溢出，这里可以放心：每一位的乘积最大是 9 × 9 = 81，而同一位置上最多累加 40 次，也就是 3240 左右，int完全装得下。所以中间数组用int就够，不需要long long。

从字符串转大数也有个小讲究。我习惯用"逐位乘 10 加当前位"的方式：从左到右扫字符串，每读一位就把当前大数整体乘 10 再加上这一位的数字。这个过程中要用一个carry变量从低位往高位传递，逻辑和乘法进位一样。特别注意全为 0 的输入，因为 0 乘 10 还是 0，没有产生任何进位，数组长度会一直是 0，必须特判——如果扫完了长度还是 0，就把值设成 0、长度设成 1。

4.3 Python 与 Java 的降维写法

如果你只是想把这道题的思路搞明白，而不是非得在 C++ 里手写高精度，那用 Python 写这道题简直是降维打击。

Python 的整数是任意精度的，int直接就能存 40 位、甚至 1000 位的数，乘法和比较都是原生支持的。同样一段 DP 逻辑，Python 版本连大数类都不用写，字符串转整数直接int(s[i-1:j])搞定，十几行代码就能 AC。

Java 的话，java.math.BigInteger提供了multiply和compareTo两个方法，也能省掉手写高精度的功夫，只是写起来比 Python 啰嗦一些。

不过我还是建议你至少手写一遍 C++ 版本。原因很现实：竞赛的默认语言还是 C++，遇到真正卡高精度的题目，你总得会写。Python 版本适合用来验证你的 DP 逻辑对不对——如果 Python 过了而 C++ 不过，那问题一定出在高精度实现上，排查方向一下子就清晰了。

这里补充一句复杂度分析，方便你判断自己的实现会不会超时。整个 DP 的乘法调用次数约为 K × N² / 2，在 K = 6、N = 40 时大约是 4800 次；每次大数乘法是 O(L²)，L 最多 80 位左右，也就是几千次基本运算。乘起来大概三千多万次基本操作，在 C++ 里是毫秒级的，完全不用担心性能。

5. 完整代码与调试现场：我在下标上栽的三个跟头

代码我给两个版本，C++ 的手写高精度版和 Python 的直球版。给完之后，重点说说我当年调试时踩过的坑，这几处比代码本身更值钱。

5.1 C++ 版本（数组存大数 + 手写乘法）

#include <bits/stdc++.h> using namespace std; const int MAXL = 105; struct Big { int d[MAXL]; // d[0] 是个位，下标越大位权越高 int len; Big() { memset(d, 0, sizeof(d)); len = 1; } // 默认值是 0 }; // 把 s[l..r] 转成大数（下标从 0 开始，闭区间） Big toBig(const string& s, int l, int r) { Big a; a.len = 0; for (int i = l; i <= r; ++i) { int carry = s[i] - '0'; // a = a * 10 + 当前位 for (int j = 0; j < a.len; ++j) { int t = a.d[j] * 10 + carry; a.d[j] = t % 10; carry = t / 10; } while (carry > 0) { a.d[a.len++] = carry % 10; carry /= 10; } } if (a.len == 0) { a.d[0] = 0; a.len = 1; } // 全 0 的特判 return a; } Big mul(const Big& a, const Big& b) { Big c; if ((a.len == 1 && a.d[0] == 0) || (b.len == 1 && b.d[0] == 0)) return c; int tmp[MAXL * 2] = {0}; for (int i = 0; i < a.len; ++i) for (int j = 0; j < b.len; ++j) tmp[i + j] += a.d[i] * b.d[j]; int len = a.len + b.len + 1; for (int i = 0; i < len; ++i) { tmp[i + 1] += tmp[i] / 10; tmp[i] %= 10; } while (len > 1 && tmp[len - 1] == 0) --len; c.len = len; for (int i = 0; i < len; ++i) c.d[i] = tmp[i]; return c; } bool bigger(const Big& a, const Big& b) { // a > b 吗 if (a.len != b.len) return a.len > b.len; for (int i = a.len - 1; i >= 0; --i) if (a.d[i] != b.d[i]) return a.d[i] > b.d[i]; return false; } int n, k; string s; Big dp[45][10]; Big num[45][45]; int main() { cin >> n >> k; cin >> s; for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) num[i][j] = toBig(s, i, j); for (int i = 1; i <= n; ++i) dp[i][0] = num[0][i - 1]; for (int j = 1; j <= k; ++j) for (int i = j + 1; i <= n; ++i) for (int t = j; t <= i - 1; ++t) { Big cand = mul(dp[t][j - 1], num[t][i - 1]); if (bigger(cand, dp[i][j])) dp[i][j] = cand; } for (int i = dp[n][k].len - 1; i >= 0; --i) cout << dp[n][k].d[i]; cout << '\n'; return 0; }

代码里num[t][i-1]这个下标最容易看晕：dp里用的是"前 i 位"这种 1 起始的计数，而num数组和字符串都是 0 起始的。前 i 位对应字符串下标0..i-1，前 t 位对应0..t-1，所以最后一段就是从下标 t 到 i-1，写成num[t][i-1]。这个问题我在下一节会专门说。

5.2 Python 版本

n, k = map(int, input().split()) s = input().strip() # num[i][j]：第 i 位到第 j 位组成的整数（1 起始的闭区间） num = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(i, n + 1): num[i][j] = int(s[i - 1:j]) dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): dp[i][0] = num[1][i] for j in range(1, k + 1): for i in range(j + 1, n + 1): for t in range(j, i): dp[i][j] = max(dp[i][j], dp[t][j - 1] * num[t + 1][i]) print(dp[n][k])

两边对照着看，能明显感觉到 Python 把所有高精度的脏活都藏起来了，剩下的骨架跟 C++ 一模一样。建议你先用 Python 把逻辑跑通，再用 C++ 重写一遍，这样调试的时候能确定问题到底是出在算法还是出在高精度实现上。

5.3 三个真实踩坑记录

坑一：num 数组的下标基准混用。我当初写 C++ 版本的时候，dp用的是 1 起始（前 i 位），结果在取最后一段的时候顺手写成了num[t + 1][i]，按照 Python 那套 1 起始的约定来写的。但 C++ 里num存的是 0 起始的字符串切片，num[t+1][i]实际取到的是从下标 t+1 到 i 的内容，正好错开了一位。表现就是样例能过（因为位数少，错位不太明显），但交上去大面积 WA。这种错误的排查方法很简单：打印中间状态，把所有dp[i][0]打出来，跟手算的前缀数值对一下，一眼就能看出来错位。

坑二：大数比较只比长度。这是我见过最高频的高精度错误。很多人写比较函数的时候图省事，只写了if (a.len != b.len) return a.len > b.len; return false;，长度相同就直接认为相等。这在本题里会直接导致答案偏小，因为两个位数相同的候选乘积会互相"顶掉"，最后留下的可能不是真正最大的那个。正确写法必须是长度相同时逐位从高位往下比。

坑三：乘法中间数组没清空、或者开小了。中间数组tmp每次调用乘法都要重新清零，如果把它写成全局变量或者static，上一次的结果会残留下来污染这一次的计算。另外数组长度也要留够，两个 40 位大数相乘，结果最多 80 位，进位之后可能到 81 位，所以我习惯开MAXL * 2也就是 210，稳一点。

还有一个不算坑但值得提的点：输出大数的时候千万别忘了逆序。因为数组是低位在前的，d[0]是个位，输出必须从len-1往下走到 0。写成从 0 到len-1输出的话，你会看到一个数字完全反过来的答案。

6. 换个问法：这道题还能怎么变形

把这道题的正解写出来只是第一步。真正让这道题的价值翻倍的，是它背后那一套"区间分割 + 决策枚举"的思维，能直接迁移到一大批变体上。这里挑几个最有代表性的说说。

6.1 至多 K 个乘号：多一层取 max 就够

如果题目改成"至多使用 K 个乘号"，答案就不是dp[n][K]了，而是max(dp[n][0], dp[n][1], ..., dp[n][K])。

为什么？因为多用一个乘号并不总是更好。举个极端的例子，数字串10、K = 1：切一刀得到1 * 0 = 0，不切得到10。显然不切更优。原因是数字串里出现了 0，任何跟 0 相乘的段都会把整个乘积拉成 0。

所以遇到"至多"这种表述，最后答案要在一个维度上再扫一遍取最大值。这个改动只有几行，但如果不注意题目到底是"恰好"还是"至多"，就会直接 WA。

6.2 要求输出切分方案：加一个决策点数组

有些变体会要求你不只输出最大乘积，还要输出具体的切分方式，比如"在第几位后面插乘号"。

这时候只需要在原来的转移里多记一个数组pre[i][j]，表示"计算dp[i][j]时选中的那个最优 t 是多少"。转移的时候，只要发现当前候选值比dp[i][j]大，就顺手把pre[i][j] = t记下来。

最后从pre[n][K]出发往前回溯：记t = pre[n][K]，那么最后一个乘号插在第 t 位后面；接着跳到状态dp[t][K-1]，取pre[t][K-1]，以此类推，直到乘号用完。回溯出来的位置序列反过来输出，就是完整的切分方案。

这个技巧的通用性极强，几乎所有输出方案的 DP 题都是这个套路：多开一个数组记录"我是从哪个状态转移过来的"。

6.3 和"石子合并""矩阵连乘"的家族关系

如果你做过经典的"石子合并"或者"矩阵连乘"，应该会有种熟悉感。那类题的状态是f[i][j]表示"把第 i 堆到第 j 堆合并成一堆的最小代价"，枚举的是"最后一次合并的分界点 k"，转移形如f[i][j] = min(f[i][k] + f[k+1][j] + 代价)。

乘积最大这道题的结构其实是一样的：枚举最后一段的起点，只不过这道题的"左半部分"是从串首开始的前缀，而不是任意区间。之所以有区别，是因为石子合并要合并成一个整体，所以左右两部分都是中间区间的形式；而乘积最大的最终结果是一条从前到后的完整划分，所以左边的状态天然就是"前缀"。

理解了这个同构关系，你会发现一大类题都能用同一套思考框架去套：确定决策动作 → 确定状态维度 → 推出转移时枚举的分界点 → 确定边界和初始化 → 处理数值溢出和精度。这套流程走顺了，区间 DP 这一类题基本就通了。

我个人在实际刷题过程中的体会是，像 1275 这种看起来简单的老题，其实是最值得反复琢磨的。它把"状态定义""枚举边界""高精度"这三个动态规划的核心考点全揉在一起了，每一处都能踩坑，每一处也都能学到东西。第一次写不出来很正常，把样例的那张 DP 表亲手推两遍，再对着代码单步走一遍，这道题就真正变成你自己的了。