信息学奥赛一本通1275 乘积最大：区间DP与高精度乘法

1. 从信息学奥赛一本通 1275 说起：这道题到底难在哪

第一次翻到信息学奥赛一本通 1275 这一页的时候，很多人会愣一下。它被安排在动态规划章节里，标题是“乘积最大”，看起来像个简单的枚举题，但真正动手写才发现坑在别处。这道题要求在一个长度最多 40 位的数字串里插入 K 个乘号，把它切成 K+1 段，让这些段的乘积尽量大。它在洛谷、各大题库里的定位是“区间划分类动态规划”的入门典型题，也是面试和竞赛中反复出现的一个思维模型，适合刚学完背包、正在过渡到区间 DP 的读者，也适合那些“DP 会写但一遇到高精度就翻车”的朋友。

这道题的价值不在 DP 本身——状态转移其实只有四五行——而在于它一次性把三个常被忽略的考点砸到你面前：怎么把“切分”抽象成阶段划分、为什么枚举顺序必须从段数角度考虑、以及当结果有四十位数字时怎么用自己的手写高精度扛住。我见过太多人在写完转移方程之后，因为long long溢出、前导零没处理、或者循环边界差了 1 而反复 WA。下面就把这道题从头到尾拆开讲，包括我踩过的那些坑。

1.1 题干还原与输入输出约束

先把原始描述摆出来，避免理解偏差。题目给一个长度为 N 的数字串，要求使用 K 个乘号把它分成 K+1 个部分，找出一种分法让这 K+1 个部分的乘积最大。输入分两行：第一行是两个自然数 N 和 K，约束是 6 ≤ N ≤ 40，1 ≤ K ≤ 6；第二行是一个长度为 N 的数字串。输出只有一个数，就是所求的最大乘积。原题还给了一个说明性例子：数字串312，N=3、K=1 时有两种分法，3*12=36和31*2=62，答案是 62。

这个例子非常关键，它暗示了一个反直觉的事实：并不是把乘号插在前面或后面更好，也不是位数越长越好，得具体算。注意题目里 N 最小是 6，最大 40，K 最大只有 6，这两个约束的组合直接决定了算法的形态。N 只有 40，说明状态空间小；K 最多 6，说明阶段数少；但 40 位数字相乘会远超 64 位整数的表示范围，这才是真正的门槛。

1.2 手算一遍，把“分法”这个词落地

要理解“分法”，最好拿312动手切一次。K=1 意味着插一个乘号，乘号可以插在 3 和 1 之间，也可以插在 1 和 2 之间，一共就两个位置。插在中间，左段是3，右段是12，乘积 36；插在右端，左段是31，右段是2，乘积 62。两个结果一比，62 更大，答案就是 62。这里有个容易忽视的细节：乘号必须插在数字之间，不能插在串头或串尾，因为那样会切出一个空段，没有意义。

再看 K=2 的情况，比如数字串1231，需要插两个乘号，切出三段。这时候可以切1*2*31=62、1*23*1=23、12*3*1=36，最大值是 62。你会发现每一段的长度组合不一样，算出来的结果也会差很多。手算的作用是让你建立“把位置当决策、把段数当阶段”的直观，这正是后面 DP 设计的思想来源。如果你连手算几步都觉得乱，那么直接上代码几乎必错。

1.3 为什么“平均分配位数”的直觉一定会翻车

很多人的第一反应是：位数差不多长，乘积应该最大。这个直觉在某些情况下是对的，但它不是普适规律。举个例子，数字串1001，K=1，插一个乘号。按“均匀”思路，切在中间得到10*01，结果 10；但如果切在最后得到100*1=100，明显更大。原因在于高位的一个 0 会极大拖累短段的值，你多留一位有效数字给某一段，往往比“平均”收益更高。

再比如9990这种串，末尾是 0，如果平均分位，99*90=8910；如果切法变成999*0=0，那就更差。所以到底怎么切最优，得靠系统地枚举所有可能，而不是靠某种“看起来合理”的经验法则。这恰恰是动态规划存在的意义：它把“全局最优切分”这件很难一眼看穿的事，拆成一堆可以递推的小问题。理解这一点，你才会明白为什么不能贪心。

2. 为什么这道题必须走动态规划这条路

搞清楚了“分法”的含义，接下来的问题是：用什么手段去搜索最优解。数字串长度 40，看似不大，但切割点的组合数随 K 增长得非常快。我们需要一种既不遗漏最优解，又能把重复计算压下去的方法，这就是动态规划的核心诉求。它靠的是问题本身具备的两个性质：最优子结构和无后效性。下面分别说说这两个性质在这道题里具体体现在哪里。

2.1 暴力枚举组合数到底有多恐怖

最朴素的做法是从 N-1 个空隙里挑 K 个位置插乘号。对于 N=40、K=6，就是从 39 个空位里挑 6 个，组合数等于 C(39,6)，算出来是 3262623。乍看三百万，好像计算机能扛，但每个方案都要做 K+1 次乘法并比较大小，而这里的“乘法”还不是普通整数乘法，而是几十位的高精度乘法，单次大约几十到上百次基本运算。乘一乘，运算量瞬间逼近上亿次，时间卡得很紧张，而且一旦 N 再大一点、K 再多一点就彻底崩了。

更麻烦的是，暴力法完全没有复用计算结果。你切12*31和切123*1里都反复用到了前缀12，每次却重新算一遍。动态规划做的就是把这些公共子结果存起来，让每个子问题的解只被求一次。所以这道题用 DP 不只是为了“优雅”，而是当规模一上来时，暴力法的性价比就迅速恶化。

2.2 最优子结构：大问题怎么拆成小问题

最优子结构说的是：如果全局最优方案是“前 t 个数字切成 j 段，后一段是剩下的”，那么这个前缀切成 j 段的方式本身也一定是最优的。为什么？假设前缀存在一个更优的切法，那么把它替换进全局方案里，总乘积只会更大，这与“全局最优”矛盾。所以最优解一定由最优子解拼出来。

这句话翻译成可操作的结论就是：只要我算出“前 i 个数字插 j-1 个乘号的最大乘积”，那么“前 i 个数字插 j 个乘号”的答案就能靠枚举最后一段的起点，从这些更小的子问题里拼出来。这就是递推的基石，也是后面写转移方程时最需要想清楚的一句话。

2.3 无后效性：为什么从前往后推是安全的

无后效性指的是，一旦确定了“前 i 个数字”“插了 j 个乘号”这个状态，后续怎么切、切出多少，都与前面具体是怎么切的无关。DP 数组里存的只是一个数值（最大乘积），不会因为你是1*23还是12*3而改变这个值。所以状态dp[i][j]是完备的，它把所有可以影响未来的信息都浓缩进了一个标量。

这一点很重要，因为它决定了循环顺序。如果我们从左往右推，计算dp[i][j]时只需要用到更小的t和j-1，这些状态都已经算好了，所以两重循环从段数到位置、从前往后推都不会出问题。理解了它，你才能放心地把 i 从 1 增大到 N，而不必担心某种“未来的切法”会回溯影响当前值。

3. 状态设计与转移方程的逐层推导

DP 的关键永远在状态定义和转移方程，这两样想清楚了，代码就是翻译。这道题的难点在于“最后一段”这个概念如何用下标表达，以及边界初始化的取值范围。我下面会用一套统一的记号，尽量避免下标混乱。你可以对照着自己在纸上画一行格子，把每一格的下标写出来。

3.1 dp[i][j] 到底代表什么

定义dp[i][j]表示：把数字串的前 i 个字符，插入 j 个乘号切分成 j+1 段之后，所能得到的最大乘积。这里“前 i 个字符”指的是从下标 0 到 i-1 的子串，不含第 i 位。用位次而不用下标，是为了让递推里的区间端点更自然。

注意 j 的含义是乘号数量，不是段数，两者差 1。之所以按乘号数来定义阶段，是因为每次转移恰恰是在已有 j-1 个乘号的方案末尾再补一个乘号。如果按段数定义，会多出一层换算，反而容易在下标上出错。我建议就按乘号数来记，写代码时心里默念“j 是乘号数”。

3.2 转移方程是怎么推出来的

切分方案的形状一定是：前 t 个字符先用 j-1 个乘号切成 j 段，然后第 t+1 到第 i 个字符单独作为最后一段。最后一段的长度至少为 1，所以 t 最大取到 i-1；同时前 t 个字符要能容得下 j-1 个乘号，至少要 j 个字符，所以 t 最小取到 j。于是枚举所有合法的 t，取其中的最大值：

dp[i][j] = max{ dp[t][j-1] * num(t+1, i) }，其中 t 从 j 到 i-1

这里num(l, r)表示把数字串第 l 到第 r 个字符（位次，从 1 开始）看成整数之后得到的值。这个乘法就是我们在高精度那一章要重点处理的地方。整个式子读下来的意思是：只要枚举“最后一段从哪开始”，前面部分已经是当前最优，最后一段固定，乘积里唯一变的就是 t，遍历一遍取最大即可。

3.3 初始化与枚举范围的细节

当 j=0，也就是一个乘号都不插的时候，前 i 个字符只能整体作为一段，所以dp[i][0]就等于num(1, i)。这是所有递推的起点，必须先把它填好。当 i 小于等于 j 的时候，前面 i 个字符插不下 j 个乘号，这些状态无意义，保持为 0（或负无穷）即可，反正不会作为有效的转移来源。

枚举范围上，外层 j 从 1 到 K，内层 i 从 j+1 到 N（因为前 i 个字符要放 j 个乘号，至少需要 j+1 个字符），最内层 t 从 j 到 i-1。答案落在dp[N][K]。这套边界看起来简单，但恰恰是最容易写错的地方，下一节我会用一张表把某个小串的完整推导过程列出来。

3.4 用一张表手推小例子，验证方程

拿数字串1231、K 最大为 2 来手推。第一列是 j=0 的初始值：dp[1][0]=1，dp[2][0]=12，dp[3][0]=123，dp[4][0]=1231。接下来算 j=1，枚举最后一段的起点：

再看 j=2，需要用到 j=1 的结果：

结果和之前手算的三个切法1*2*31=62、1*23*1=23、12*3*1=36完全一致，最大是 62。表格推一遍之后，你会对“t 是最后一段起点”这个角色印象非常深，代码里也就不会把 t 和 i 弄混了。

4. 真正卡人的地方：高精度运算

转移方程写完之后，很多人会顺手用long long存dp，然后交上去 WA 一半。原因不是逻辑错，而是数值存不下。这一节我们把溢出这件事算清楚，再讲怎么用手写高精度把它接住，最后顺便给一个用 Python 偷懒的写法，供不同语言的读者参考。这部分是这道题含金量最高、也最容易被忽略的地方。

4.1 long long 到底能装多少位

long long通常是有符号 64 位整数，能表示的最大值约 9.22×10^18，也就是 19 位十进制数。而这道题 N 可以到 40，如果 K 比较小，某一整段可能长达 30 位以上。比如 40 个 9 组成的串，K=1 时最长的切法是 20 位乘 20 位，结果约 10^40 量级，远远溢出。有人会想换成__int128，它大约能表示 1.7×10^38，还是不够。所以任何内置整数类型在这道题的极端数据面前都站不住，必须自己实现大整数。

这一点其实是这道题最“阴”的地方：大部分测试点的值没这么大，用long long能过很多数据，于是你很难意识到问题所在，只有个别极限测试点会把正确解和错误解区分开。这也是为什么对拍和小数据验证特别重要，之后会讲。

4.2 手写高精度的结构体设计

我习惯用一个结构体来存大整数，内部用数组按低位到高位存储每一位数字，另用一个len记录实际有效位数。为什么要低位在低位数组索引上？因为乘法要从低位往高位进位，这样写循环最顺。结构体大概是这样的：

struct BigNum { int len; int d[105]; BigNum() { len = 1; memset(d, 0, sizeof(d)); } };

d[1]存个位，d[2]存十位，以此类推，d[0]空着不用。数组长度开到 105 是因为 40 位乘以 40 位最多 80 位，留出富余量。这个设计的好处是乘法可以直接按十进制竖式处理，不需要处理二进制分组，逻辑直观，调试也方便。

4.3 高精度乘法怎么写才不出错

乘法模仿竖式：先让每一位两两相乘，把结果按位累加到对应位置，再统一从低位到高位处理进位。关键代码结构如下：

BigNum mul(const BigNum &a, const BigNum &b) { BigNum c; c.len = a.len + b.len; for (int i = 1; i <= a.len; i++) for (int j = 1; j <= b.len; j++) c.d[i + j - 1] += a.d[i] * b.d[j]; for (int i = 1; i <= c.len; i++) { c.d[i + 1] += c.d[i] / 10; c.d[i] %= 10; } while (c.len > 1 && c.d[c.len] == 0) c.len--; return c; }

第一个循环做的是“错位累加”，i+j-1这个下标正是两个幂次相加后对应的十进制位。第二个循环统一处理进位，避免每一位都要重复判断。最后那个while很重要，它去掉高位的无效零，否则算出来的位数会虚高，影响后面的比较。

注意：两个循环不要合并着写，先全部累加再统一进位，逻辑更清晰，也避免了“进位后影响后面相乘项”的隐患。这是高精度乘法的常见写法，值得背下来。

4.4 比较函数与前导零陷阱

比较大小时，先比位数，位数多的那个一定更大；位数相同再从最高位往下逐位比。这个思路没有问题，但前提是每一位的位数都是“真实有效位数”。这里就埋着一个大坑：如果有人把数字串里的前导零也当有效位，长度就会失真。比如字符串"001"，字面上是三位，值其实是 1，如果不处理，len=3就会让它比真实值更大的数还要“长”。

所以把一个子串转成大整数时，必须去掉高位零，只保留真正的有效位数。这个处理看起来琐碎，但如果没有做，一些包含零前缀的测试点就会给出错误答案，而且错误方式非常隐蔽：数值对，但比较时判错了。我在 4.2 的结构体里没有直接放这个逻辑，是因为它属于转换函数，下面实现部分会专门处理。

5. 从零写出可提交的完整代码

前面把原理讲透了，现在到了动手环节。我按“转换子串、DP 主循环、输出答案”的顺序组织代码，每一步都会标注它在解决什么问题。这里给出 C++ 的完整实现，因为一本通的题大多以 C++ 为主。同时也附上 Python 的等价写法，方便习惯用 Python 的读者做对拍或者快速验证思路。

5.1 子串转大整数的预处理

把子串s[l..r]（位次制，从 1 开始）转成BigNum，去掉前导零，代码是这样的：

BigNum fromStr(int l, int r, const string &s) { BigNum a; a.len = r - l + 1; for (int i = 0; i < a.len; i++) a.d[a.len - i] = s[l - 1 + i] - '0'; while (a.len > 1 && a.d[a.len] == 0) a.len--; return a; }

注意s[l-1+i]这个下标换算：位次从 1 开始，所以字符串索引要减 1。这一段最容易写反，写完之后一定用小例子验证，比如fromStr(1,3,"001")应该得到长度为 1、值为 1 的结果。

5.2 DP 主循环的完整写法

主循环部分把前面推导的转移方程原样翻译出来：

int n, k; string s; BigNum dp[45][10]; int main() { cin >> n >> k >> s; for (int i = 1; i <= n; i++) dp[i][0] = fromStr(1, i, s); for (int j = 1; j <= k; j++) { for (int i = j + 1; i <= n; i++) { for (int t = j; t < i; t++) { BigNum cand = mul(dp[t][j - 1], fromStr(t + 1, i, s)); if (lessThan(dp[i][j], cand)) dp[i][j] = cand; } } } for (int i = dp[n][k].len; i >= 1; i--) cout << dp[n][k].d[i]; cout << endl; return 0; }

这里dp[i][j]初值是 0（长度为 1、值为 0），任何正数都比它大，所以第一次一定会被更新，不用额外赋负无穷。lessThan就是上一节的比较函数。外层 j 表示乘号数，内层 i 表示前缀长度，最内层 t 是最后一段的起点，三层循环对应上一章的枚举顺序，没有任何花哨的技巧。

5.3 Python 的偷懒写法

如果只是验证思路或做对拍，Python 的大整数可以省掉所有高精度代码：

n, k = map(int, input().split()) s = input().strip() dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): dp[i][0] = int(s[: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] * int(s[t:i])) print(dp[n][k])

s[t:i]取的是下标 t 到 i-1 的子串，刚好对应位次 t+1 到 i。Python 的整数天然支持任意精度，所以int()之后直接乘不会有溢出问题，非常适合做正确答案的对照。

提示：理解能力强的读者会发现，用int(s[:i])和int(s[t:i])完全绕开了前导零问题，因为 Python 自己会正确解析。C++ 写的同学就要自己处理那个while去零逻辑，这是语言差异带来的额外工作量。

6. 调试实录：常见错误与排查思路

代码敲完只是开始，真正消耗时间的是调试。这道题的 WA 往往落在几个非常固定的地方，我把它们整理成一张速查表，配合排查思路一起讲。如果你卡住了，先照表逐条对，多半能定位问题。最后再分享两个我自己踩过的坑，都是文档里不会写的细节。

6.1 常见错误速查表

这张表基本覆盖了九成以上的常见问题。最隐蔽的一类是“数值对但位数错”，它不会让答案变成别的数，只会在比较时判定错误，导致某一步选了次优方案。

6.2 用对拍把错误数据逼出来

我最推荐的调试方法是对拍：写一个 Python 的暴力版本，用itertools.combinations枚举所有切分位置，用小数据（比如 N=6 到 10，K=1 到 3）随机生成数字串，跑几百组，和 C++ 的输出逐行比对。只要有一组不一致，就能立刻定位到让你出错的输入。这个方法比盯着代码找 bug 快得多，特别是当问题出在边界或溢出时。

生成随机串时，不要只生成没有零的串，故意混入零和前导零，能很快把fromStr里没处理的边界暴露出来。我自己第一次做这道题时，就是靠对拍发现前导零那个坑的。

6.3 我踩过的两个坑

第一个坑是把位次和下标混用。上面强调过fromStr里s[l-1+i]的换算，我当初图省事，直接传字符串下标进去，结果某个位次边界上差了一位，导致某些测试点答案偏小一点。后来我强制所有函数统一使用“位次制，从 1 开始”，转换只发生在读取字符串那一刻，代码就清爽了。

第二个坑是数组开小了。一开始d[50]以为够了，但 40 位乘 40 位实际要 80 位，乘法结果在高位被截断，输出少了几位。这种错误在部分数据下看不出来，一到极限就崩。后来我把数组开到 105，并且习惯在写完高精度后先用最长的情况测一遍，才算稳当。

注意：高精度题的数组大小一律按“最长情况 + 冗余”来开，宁大勿小。这道题最长乘积约 80 位，开 100 以上完全没负担，别在这里省空间。

最后分享一个我觉得挺实用的小技巧。如果你在做这道题时总是记不住dp[i][j]里 j 到底是乘号数还是段数，就在纸上把1231那个表格默写一遍——写两三次之后，这个下标关系就永久印在脑子里了。它不只适用于 1275 这一题，后面遇到“把数组分成若干段”“插入若干分隔符”的同类题，你都能直接套用这套“枚举最后一段起点”的框架，这才是这道题真正想教给你的东西。