1. 从信息学奥赛一本通 1275 说起这道题到底难在哪第一次翻到信息学奥赛一本通 1275 这一页的时候很多人会愣一下。它被安排在动态规划章节里标题是“乘积最大”看起来像个简单的枚举题但真正动手写才发现坑在别处。这道题要求在一个长度最多 40 位的数字串里插入 K 个乘号把它切成 K1 段让这些段的乘积尽量大。它在洛谷、各大题库里的定位是“区间划分类动态规划”的入门典型题也是面试和竞赛中反复出现的一个思维模型适合刚学完背包、正在过渡到区间 DP 的读者也适合那些“DP 会写但一遇到高精度就翻车”的朋友。这道题的价值不在 DP 本身——状态转移其实只有四五行——而在于它一次性把三个常被忽略的考点砸到你面前怎么把“切分”抽象成阶段划分、为什么枚举顺序必须从段数角度考虑、以及当结果有四十位数字时怎么用自己的手写高精度扛住。我见过太多人在写完转移方程之后因为long long溢出、前导零没处理、或者循环边界差了 1 而反复 WA。下面就把这道题从头到尾拆开讲包括我踩过的那些坑。1.1 题干还原与输入输出约束先把原始描述摆出来避免理解偏差。题目给一个长度为 N 的数字串要求使用 K 个乘号把它分成 K1 个部分找出一种分法让这 K1 个部分的乘积最大。输入分两行第一行是两个自然数 N 和 K约束是 6 ≤ N ≤ 401 ≤ K ≤ 6第二行是一个长度为 N 的数字串。输出只有一个数就是所求的最大乘积。原题还给了一个说明性例子数字串312N3、K1 时有两种分法3*1236和31*262答案是 62。这个例子非常关键它暗示了一个反直觉的事实并不是把乘号插在前面或后面更好也不是位数越长越好得具体算。注意题目里 N 最小是 6最大 40K 最大只有 6这两个约束的组合直接决定了算法的形态。N 只有 40说明状态空间小K 最多 6说明阶段数少但 40 位数字相乘会远超 64 位整数的表示范围这才是真正的门槛。1.2 手算一遍把“分法”这个词落地要理解“分法”最好拿312动手切一次。K1 意味着插一个乘号乘号可以插在 3 和 1 之间也可以插在 1 和 2 之间一共就两个位置。插在中间左段是3右段是12乘积 36插在右端左段是31右段是2乘积 62。两个结果一比62 更大答案就是 62。这里有个容易忽视的细节乘号必须插在数字之间不能插在串头或串尾因为那样会切出一个空段没有意义。再看 K2 的情况比如数字串1231需要插两个乘号切出三段。这时候可以切1*2*3162、1*23*123、12*3*136最大值是 62。你会发现每一段的长度组合不一样算出来的结果也会差很多。手算的作用是让你建立“把位置当决策、把段数当阶段”的直观这正是后面 DP 设计的思想来源。如果你连手算几步都觉得乱那么直接上代码几乎必错。1.3 为什么“平均分配位数”的直觉一定会翻车很多人的第一反应是位数差不多长乘积应该最大。这个直觉在某些情况下是对的但它不是普适规律。举个例子数字串1001K1插一个乘号。按“均匀”思路切在中间得到10*01结果 10但如果切在最后得到100*1100明显更大。原因在于高位的一个 0 会极大拖累短段的值你多留一位有效数字给某一段往往比“平均”收益更高。再比如9990这种串末尾是 0如果平均分位99*908910如果切法变成999*00那就更差。所以到底怎么切最优得靠系统地枚举所有可能而不是靠某种“看起来合理”的经验法则。这恰恰是动态规划存在的意义它把“全局最优切分”这件很难一眼看穿的事拆成一堆可以递推的小问题。理解这一点你才会明白为什么不能贪心。2. 为什么这道题必须走动态规划这条路搞清楚了“分法”的含义接下来的问题是用什么手段去搜索最优解。数字串长度 40看似不大但切割点的组合数随 K 增长得非常快。我们需要一种既不遗漏最优解又能把重复计算压下去的方法这就是动态规划的核心诉求。它靠的是问题本身具备的两个性质最优子结构和无后效性。下面分别说说这两个性质在这道题里具体体现在哪里。2.1 暴力枚举组合数到底有多恐怖最朴素的做法是从 N-1 个空隙里挑 K 个位置插乘号。对于 N40、K6就是从 39 个空位里挑 6 个组合数等于 C(39,6)算出来是 3262623。乍看三百万好像计算机能扛但每个方案都要做 K1 次乘法并比较大小而这里的“乘法”还不是普通整数乘法而是几十位的高精度乘法单次大约几十到上百次基本运算。乘一乘运算量瞬间逼近上亿次时间卡得很紧张而且一旦 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 个乘号切分成 j1 段之后所能得到的最大乘积。这里“前 i 个字符”指的是从下标 0 到 i-1 的子串不含第 i 位。用位次而不用下标是为了让递推里的区间端点更自然。注意 j 的含义是乘号数量不是段数两者差 1。之所以按乘号数来定义阶段是因为每次转移恰恰是在已有 j-1 个乘号的方案末尾再补一个乘号。如果按段数定义会多出一层换算反而容易在下标上出错。我建议就按乘号数来记写代码时心里默念“j 是乘号数”。3.2 转移方程是怎么推出来的切分方案的形状一定是前 t 个字符先用 j-1 个乘号切成 j 段然后第 t1 到第 i 个字符单独作为最后一段。最后一段的长度至少为 1所以 t 最大取到 i-1同时前 t 个字符要能容得下 j-1 个乘号至少要 j 个字符所以 t 最小取到 j。于是枚举所有合法的 t取其中的最大值dp[i][j] max{ dp[t][j-1] * num(t1, i) }其中 t 从 j 到 i-1这里num(l, r)表示把数字串第 l 到第 r 个字符位次从 1 开始看成整数之后得到的值。这个乘法就是我们在高精度那一章要重点处理的地方。整个式子读下来的意思是只要枚举“最后一段从哪开始”前面部分已经是当前最优最后一段固定乘积里唯一变的就是 t遍历一遍取最大即可。3.3 初始化与枚举范围的细节当 j0也就是一个乘号都不插的时候前 i 个字符只能整体作为一段所以dp[i][0]就等于num(1, i)。这是所有递推的起点必须先把它填好。当 i 小于等于 j 的时候前面 i 个字符插不下 j 个乘号这些状态无意义保持为 0或负无穷即可反正不会作为有效的转移来源。枚举范围上外层 j 从 1 到 K内层 i 从 j1 到 N因为前 i 个字符要放 j 个乘号至少需要 j1 个字符最内层 t 从 j 到 i-1。答案落在dp[N][K]。这套边界看起来简单但恰恰是最容易写错的地方下一节我会用一张表把某个小串的完整推导过程列出来。3.4 用一张表手推小例子验证方程拿数字串1231、K 最大为 2 来手推。第一列是 j0 的初始值dp[1][0]1dp[2][0]12dp[3][0]123dp[4][0]1231。接下来算 j1枚举最后一段的起点状态t 取值候选乘积结果dp[2][1]t11 × num(2,2)1×222dp[3][1]t1; t21×2323; 12×33636dp[4][1]t1; t2; t31×231231; 12×31372; 123×1123372再看 j2需要用到 j1 的结果状态t 取值候选乘积结果dp[4][2]t2; t32×3162; 36×13662结果和之前手算的三个切法1*2*3162、1*23*123、12*3*136完全一致最大是 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 组成的串K1 时最长的切法是 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; }第一个循环做的是“错位累加”ij-1这个下标正是两个幂次相加后对应的十进制位。第二个循环统一处理进位避免每一位都要重复判断。最后那个while很重要它去掉高位的无效零否则算出来的位数会虚高影响后面的比较。注意两个循环不要合并着写先全部累加再统一进位逻辑更清晰也避免了“进位后影响后面相乘项”的隐患。这是高精度乘法的常见写法值得背下来。4.4 比较函数与前导零陷阱比较大小时先比位数位数多的那个一定更大位数相同再从最高位往下逐位比。这个思路没有问题但前提是每一位的位数都是“真实有效位数”。这里就埋着一个大坑如果有人把数字串里的前导零也当有效位长度就会失真。比如字符串001字面上是三位值其实是 1如果不处理len3就会让它比真实值更大的数还要“长”。所以把一个子串转成大整数时必须去掉高位零只保留真正的有效位数。这个处理看起来琐碎但如果没有做一些包含零前缀的测试点就会给出错误答案而且错误方式非常隐蔽数值对但比较时判错了。我在 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-1i]这个下标换算位次从 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 的子串刚好对应位次 t1 到 i。Python 的整数天然支持任意精度所以int()之后直接乘不会有溢出问题非常适合做正确答案的对照。提示理解能力强的读者会发现用int(s[:i])和int(s[t:i])完全绕开了前导零问题因为 Python 自己会正确解析。C 写的同学就要自己处理那个while去零逻辑这是语言差异带来的额外工作量。6. 调试实录常见错误与排查思路代码敲完只是开始真正消耗时间的是调试。这道题的 WA 往往落在几个非常固定的地方我把它们整理成一张速查表配合排查思路一起讲。如果你卡住了先照表逐条对多半能定位问题。最后再分享两个我自己踩过的坑都是文档里不会写的细节。6.1 常见错误速查表现象可能原因排查方向部分点 WA值偏小用了 long long 或 int 溢出换成 BigNum 或 Python全部 WA答案很小循环边界写反t 从 0 开始确认 t 从 j 开始枚举答案位数异常多前导零没去掉检查 fromStr 的去零循环输出多一个 0输出时按 len 到 1 顺序没控制好确认从最高位往下打印小数据对大数据错多数是溢出不是逻辑用小数据先对拍验证j0 结果不对dp[i][0] 初始化错误单独检查初始化循环这张表基本覆盖了九成以上的常见问题。最隐蔽的一类是“数值对但位数错”它不会让答案变成别的数只会在比较时判定错误导致某一步选了次优方案。6.2 用对拍把错误数据逼出来我最推荐的调试方法是对拍写一个 Python 的暴力版本用itertools.combinations枚举所有切分位置用小数据比如 N6 到 10K1 到 3随机生成数字串跑几百组和 C 的输出逐行比对。只要有一组不一致就能立刻定位到让你出错的输入。这个方法比盯着代码找 bug 快得多特别是当问题出在边界或溢出时。生成随机串时不要只生成没有零的串故意混入零和前导零能很快把fromStr里没处理的边界暴露出来。我自己第一次做这道题时就是靠对拍发现前导零那个坑的。6.3 我踩过的两个坑第一个坑是把位次和下标混用。上面强调过fromStr里s[l-1i]的换算我当初图省事直接传字符串下标进去结果某个位次边界上差了一位导致某些测试点答案偏小一点。后来我强制所有函数统一使用“位次制从 1 开始”转换只发生在读取字符串那一刻代码就清爽了。第二个坑是数组开小了。一开始d[50]以为够了但 40 位乘 40 位实际要 80 位乘法结果在高位被截断输出少了几位。这种错误在部分数据下看不出来一到极限就崩。后来我把数组开到 105并且习惯在写完高精度后先用最长的情况测一遍才算稳当。注意高精度题的数组大小一律按“最长情况 冗余”来开宁大勿小。这道题最长乘积约 80 位开 100 以上完全没负担别在这里省空间。最后分享一个我觉得挺实用的小技巧。如果你在做这道题时总是记不住dp[i][j]里 j 到底是乘号数还是段数就在纸上把1231那个表格默写一遍——写两三次之后这个下标关系就永久印在脑子里了。它不只适用于 1275 这一题后面遇到“把数组分成若干段”“插入若干分隔符”的同类题你都能直接套用这套“枚举最后一段起点”的框架这才是这道题真正想教给你的东西。