1. 從 1231 這組樣例出發(fā)為什么暴力枚舉會(huì)被卡死在信息學(xué)奧賽一本通的動(dòng)態(tài)規(guī)劃章節(jié)里編號(hào) 1275 的【例9.19】乘積最大是一道被無數(shù)人反復(fù)講、又反復(fù)講錯(cuò)的題。它出自早年的 NOIP 提高組題面樸素得像小學(xué)奧數(shù)給一個(gè)長(zhǎng)度為 N 的數(shù)字串再給 K 個(gè)乘號(hào)要求把這 K 個(gè)乘號(hào)全部插進(jìn)數(shù)字串的縫隙里使分出來的 K1 個(gè)部分相乘的結(jié)果最大。這道題的輸入只有兩行輸出只有一個(gè)整數(shù)看起來五分鐘就能寫完但真正動(dòng)手的人很快會(huì)發(fā)現(xiàn)兩個(gè)問題一是怎么切才最優(yōu)靠人眼試根本試不出來二是當(dāng) N 最大到 40 的時(shí)候答案會(huì)膨脹到 40 位以上用long long存結(jié)果直接溢出。這篇內(nèi)容我不打算只貼一份代碼就完事。和平常寫題解不一樣我更想把為什么狀態(tài)要這么定義為什么枚舉范圍只能這么取為什么高精度不是可選優(yōu)化而是必需品這幾件事說透。因?yàn)榘堰@道題吃下來你順手就能拿下后面一大類區(qū)間決策類的問題投入產(chǎn)出比很高。1.1 三個(gè)容易讀漏的題目約束先把題目條件逐條羅列清楚這三條里任何一條看漏代碼都過不了。第一乘號(hào)必須恰好用完。題目說的是使用 K 個(gè)乘號(hào)不是至多 K 個(gè)。這意味著分出來的段數(shù)固定是 K1 段每一段至少得有 1 位數(shù)字。這是后面枚舉范圍推導(dǎo)的直接依據(jù)。第二數(shù)字串的長(zhǎng)度 N 可能到 40。數(shù)據(jù)范圍大致是 6 ≤ N ≤ 401 ≤ K ≤ 6且 K N。40 位數(shù)字切 7 段最后乘積的量級(jí)在 10 的 40 次方上下而long long的極限只有約 9.2 × 10 的 18 次方連尾數(shù)都比不上。所以這道題的正解必須自帶高精度。第三數(shù)字串里可能出現(xiàn) 0。很多人在寫狀態(tài)初值的時(shí)候習(xí)慣用-1表示這個(gè)狀態(tài)還沒被算過結(jié)果遇到含 0 的數(shù)據(jù)就翻車——因?yàn)檎鎸?shí)的乘積就是 0跟你用來表示未計(jì)算的哨兵值撞車了。這個(gè)坑我在后面會(huì)單獨(dú)說。樣例輸入是4 2加一行1231樣例輸出是62。切法是1 * 2 * 31。你可以自己驗(yàn)算一下其他兩種切法1 * 23 * 1 2312 * 3 * 1 36確實(shí)都不如 62。1.2 讓兩段盡量勻的直覺為什么一定會(huì)錯(cuò)大部分人第一次做這道題腦子里會(huì)冒出一個(gè)貪心既然要讓乘積最大那讓每一段的數(shù)值盡量接近不就行了這就是小學(xué)里和一定、差越小積越大的直覺。這個(gè)直覺在兩個(gè)數(shù)的場(chǎng)合是對(duì)的但一旦段數(shù)變多、而且還要考慮數(shù)位長(zhǎng)度對(duì)數(shù)值的影響它就完全失效了。舉個(gè)能直接打臉的例子數(shù)字串1119K 1也就是只切一刀。三種切法分別是 1 × 119 119、11 × 19 209、111 × 9 999。按盡量勻的直覺應(yīng)該選 11 × 19 209但真實(shí)最優(yōu)是 111 × 9 999差了將近五倍。為什么會(huì)這樣因?yàn)樵谶@個(gè)數(shù)字串里末位那個(gè) 9 是唯一的大數(shù)因子把它單獨(dú)切出來當(dāng)乘數(shù)收益遠(yuǎn)大于讓兩段位數(shù)接近。數(shù)字的大小是由高位主導(dǎo)的而位數(shù)接近只是看起來勻跟數(shù)值均衡完全是兩碼事。更有意思的是同一組數(shù)字串在不同 K 下最優(yōu)切點(diǎn)會(huì)跳到完全不同的位置。還是1231K 1 時(shí)最優(yōu)是12 * 31 372切在中間K 2 時(shí)最優(yōu)卻是1 * 2 * 31 62切在靠前的位置。同一串?dāng)?shù)字乘號(hào)個(gè)數(shù)一變最優(yōu)結(jié)構(gòu)就變了。這就說明不存在一個(gè)固定的貪心規(guī)則能覆蓋所有情況必須老老實(shí)實(shí)做決策搜索。1.3 枚舉所有切法的代價(jià)C(39,6) 不是一個(gè)小數(shù)字有人會(huì)想那我把所有切法枚舉一遍不就行了N 40 的時(shí)候一共有 39 個(gè)空隙從中選 K 6 個(gè)位置放乘號(hào)組合數(shù)是 C(39, 6) 3262623三百多萬(wàn)種。單看這個(gè)數(shù)字好像還在可接受范圍內(nèi)——如果每次切分只需要一次整數(shù)乘法的話確實(shí)如此。但問題恰恰在于每一次切分你都要做 6 次高精度乘法而每個(gè)大數(shù)可能有 40 位左右。手寫大數(shù)乘法是 O(L2) 的L ≈ 40一次就是 1600 次基本運(yùn)算6 次乘法加起來接近一萬(wàn)次。總運(yùn)算量大約是 3262623 × 10000 ≈ 3.3 × 10 的 10 次方這個(gè)量級(jí)在競(jìng)賽的 1 秒時(shí)限里是絕對(duì)過不去的。而用動(dòng)態(tài)規(guī)劃來做需要執(zhí)行的乘法次數(shù)只有幾千次——具體來說是三層循環(huán)枚舉狀態(tài)和決策點(diǎn)的組合數(shù)大概是 K × N2 / 2 ≈ 4800 次。從三千萬(wàn)次運(yùn)算降到五千次這就是為什么這道題必須用 DP而不是靠枚舉加剪枝硬扛。2. dp[i][j] 這個(gè)狀態(tài)不是拍腦袋定的動(dòng)態(tài)規(guī)劃最難的從來不是寫轉(zhuǎn)移方程而是想清楚狀態(tài)該怎么定義。很多人背下了這道題的dp[i][j]表示前 i 個(gè)數(shù)字里插 j 個(gè)乘號(hào)但問他為什么這么定答不上來。我把自己當(dāng)初推導(dǎo)的過程完整復(fù)述一遍希望能幫你建立狀態(tài)是被問題結(jié)構(gòu)逼出來的這種感覺。2.1 決策動(dòng)作到底是選數(shù)字還是切位置很多人一看到乘積最大第一反應(yīng)是把狀態(tài)定義成選到第幾個(gè)數(shù)字為止然后糾結(jié)于這個(gè)數(shù)字到底屬于哪一段。這就是走偏了。重新讀一遍題目數(shù)字串的順序是不能打亂的你能做的唯一動(dòng)作就是在某些縫隙里插入乘號(hào)。所以真正意義上的決策是第 i 個(gè)數(shù)字后面到底切不切。換句話說問題的解是一組切分位置的集合而不是一組數(shù)字的排列。一旦意識(shí)到?jīng)Q策對(duì)象是切分點(diǎn)狀態(tài)的形狀就清晰了我們需要記錄的核心信息是已經(jīng)處理到了數(shù)字串的第幾位以及已經(jīng)用掉了幾個(gè)乘號(hào)。前者決定了還剩哪些數(shù)字可用后者決定了還剩幾個(gè)乘號(hào)要放。這兩個(gè)維度合起來就組成了dp[i][j]。2.2 為什么按前綴長(zhǎng)度的劃分天然滿足無后效性動(dòng)態(tài)規(guī)劃能不能成立關(guān)鍵看狀態(tài)轉(zhuǎn)移有沒有后效性。所謂無后效性就是一旦到達(dá)某個(gè)狀態(tài)未來的決策只跟這個(gè)狀態(tài)本身有關(guān)跟你是怎么走到這里的無關(guān)。對(duì)于這道題dp[i][j]表示把前 i 個(gè)數(shù)字分成 j1 段的最大乘積。注意這里的關(guān)鍵點(diǎn)前 i 個(gè)數(shù)字被劃分成 j1 段之后后面剩下的數(shù)字串第 i1 位到第 N 位該怎么切跟前面這 j1 段具體是怎么分的沒有關(guān)系。因?yàn)槟阒恍枰狼懊婺遣糠值淖畲蟪朔e是多少后面部分的最優(yōu)切法不受影響它們之間唯一的耦合就是乘起來這個(gè)動(dòng)作。這就滿足了最優(yōu)子結(jié)構(gòu)全局最優(yōu)解一定能拆成一個(gè)前綴最優(yōu)解乘上一段后綴數(shù)字。反過來說如果你把狀態(tài)定義成第 i 個(gè)數(shù)字所在的段是從第幾位開始的那狀態(tài)的維度就爆炸了而且也不滿足無后效性因?yàn)楹罄m(xù)切分要依賴的具體分段信息太多了。2.3 初始化dp[i][0] 與無解狀態(tài)的處理選擇狀態(tài)定好之后邊界條件就順理成章了。dp[i][0]表示前 i 個(gè)數(shù)字里一個(gè)乘號(hào)都不放那就只有一個(gè)段值就是前 i 位數(shù)字組成的那個(gè)整數(shù)。比如樣例里的1231dp[1][0] 1dp[2][0] 12dp[3][0] 123dp[4][0] 1231。這個(gè)初始化用高精度直接對(duì)字符串切片轉(zhuǎn)換就行非常直觀。至于無解狀態(tài)有兩種常見寫法。一種是把整個(gè) dp 數(shù)組初始化為 0因?yàn)槌朔e的最小可能值就是 00 作為一個(gè)合法的當(dāng)前最大候選值不會(huì)造成任何錯(cuò)誤——任何正數(shù)都會(huì)把它頂?shù)舳绻泻蜻x都算出來是 0那說明數(shù)字串里全是 0答案本來就是 0。另一種是初始化為 -1 當(dāng)作哨兵轉(zhuǎn)移時(shí)特判。我強(qiáng)烈建議第一種理由很實(shí)在這題的乘積天然是非負(fù)的0 本身就是合法值域的下界用它當(dāng)初始值既省代碼又不會(huì)誤判而 -1 哨兵反而會(huì)在含 0 的數(shù)據(jù)上制造歧義。這里還有個(gè)容易忽略的細(xì)節(jié)dp[i][j]只對(duì) j i 有意義。因?yàn)橐亚?i 個(gè)數(shù)字切成 j1 段每段至少 1 位所以必須滿足 i ≥ j1。對(duì)于 i ≤ j 的狀態(tài)我們根本不會(huì)去訪問也就不用管。3. 轉(zhuǎn)移方程里枚舉點(diǎn) t 的上下界寫錯(cuò)一個(gè)就 WA轉(zhuǎn)移方程本身不長(zhǎng)但那個(gè)枚舉變量的取值范圍是這道題最容易寫錯(cuò)的地方。我見過太多人把下界寫成 1結(jié)果要么數(shù)組越界要么算出莫名其妙的答案。3.1 把最后一段單獨(dú)拎出來推導(dǎo)轉(zhuǎn)移方程的標(biāo)準(zhǔn)姿勢(shì)是思考最后一步做了什么決策。當(dāng)我們計(jì)算dp[i][j]前 i 個(gè)數(shù)字插 j 個(gè)乘號(hào)分成 j1 段時(shí)考慮最后一個(gè)乘號(hào)插在哪里。假設(shè)它插在第 t 個(gè)數(shù)字之后那么整個(gè)串就被切成了兩部分前面是前 t 個(gè)數(shù)字后面是從第 t1 位到第 i 位的這一段。前面那部分需要插 j-1 個(gè)乘號(hào)也就是dp[t][j-1]后面那部分是固定的一個(gè)整數(shù)記為num(t1, i)。于是轉(zhuǎn)移方程就是dp[i][j] max{ dp[t][j-1] * num(t1, i) }對(duì)所有合法的 t 取最大值這里的num(t1, i)表示數(shù)字串從第 t1 位到第 i 位組成的那個(gè)整數(shù)。整個(gè)思路就是把最后一段的起點(diǎn)在哪里枚舉一遍這是所有區(qū)間分割類 DP 的通用套路。3.2 下界為什么是 j 而不是 1現(xiàn)在來說枚舉范圍。t 的取值范圍必須是[j, i-1]這兩個(gè)邊界都有明確的現(xiàn)實(shí)含義。先說下界 t ≥ j。因?yàn)閐p[t][j-1]要求把前 t 個(gè)數(shù)字分成 j 段插 j-1 個(gè)乘號(hào)而分成 j 段至少需要 j 個(gè)數(shù)字。如果 t j這個(gè)狀態(tài)根本沒有意義強(qiáng)行訪問會(huì)讀到未初始化的垃圾值在 C 里就是默認(rèn)的 0會(huì)讓答案偏小。這就是為什么下界是 j而不是想當(dāng)然的 1。再說上界 t ≤ i-1。因?yàn)樽詈笠欢蝞um(t1, i)至少要包含 1 位數(shù)字所以 t 最多到 i-1。如果寫成 t ≤ i那就切出一段空的num(i1, i)在字符串上是個(gè)非法區(qū)間轉(zhuǎn)換出來直接錯(cuò)。順帶說一句外層循環(huán)的順序必須是先枚舉 j再枚舉 i。因?yàn)閐p[i][j]依賴的是dp[t][j-1]也就是乘號(hào)個(gè)數(shù)少一層的狀態(tài)。只有當(dāng)所有 j-1 層的結(jié)果都算完了才能算第 j 層。3.3 手推 1231 的完整 DP 表光看公式還是虛我們拿樣例1231、K 2 手動(dòng)跑一遍把整張表填出來。數(shù)字串各位分別是 1、2、3、1。先算所有區(qū)間數(shù)值num(1,1)1num(2,2)2num(3,3)3num(4,4)1num(1,2)12num(2,3)23num(3,4)31num(1,3)123num(2,4)231num(1,4)1231。i前 i 位dp[i][0]dp[i][1]dp[i][2]11——2122—31233664123137262逐格解釋一下第 1 層j 1的計(jì)算dp[2][1]t 只能取 1dp[1][0] * num(2,2) 1 * 2 2。dp[3][1]t 取 1 得1 * num(2,3) 1 * 23 23t 取 2 得dp[2][0] * num(3,3) 12 * 3 36。取最大值 36。dp[4][1]t 取 1 得1 * 231 231t 取 2 得12 * 31 372t 取 3 得123 * 1 123。取最大值 372。再看第 2 層j 2注意此時(shí) t 的下界是 2dp[3][2]t 只能取 2dp[2][1] * num(3,3) 2 * 3 6。dp[4][2]t 取 2 得dp[2][1] * num(3,4) 2 * 31 62t 取 3 得dp[3][1] * num(4,4) 36 * 1 36。取最大值 62。最終答案dp[4][2] 62跟樣例輸出完全對(duì)上。把這個(gè)表親手推一遍比看十遍方程都管用——你能親眼看到 t 的下界是怎么隨著 j 往上走的。4. 40 位數(shù)字的乘積有多大高精度不是可選項(xiàng)前面提到高精度這里展開講清楚為什么這道題繞不過去以及手寫大數(shù)到底要寫哪些東西。4.1 量級(jí)估算為什么 long long 一定會(huì)炸先做一個(gè)粗算讓你對(duì)答案的大小有個(gè)概念。N 40、K 6也就是把 40 位數(shù)字切成 7 段。根據(jù)分段越均勻乘積越大的規(guī)律這個(gè)是針對(duì)位數(shù)成立的經(jīng)驗(yàn)規(guī)律和前面說的數(shù)值均衡不一樣7 段大致是每段 5 到 6 位。假設(shè)數(shù)字串里全是 940 位切 7 段比較合理的分法是 6666655 40。每段的數(shù)值大概在 10 的 5 次方到 10 的 6 次方之間7 段乘起來量級(jí)大約是 10 的 40 次方左右。這意味著答案有 40 位左右的十進(jìn)制數(shù)字。long long能表示的最大值約是 9.22 × 10 的 18 次方也就是 19 位十進(jìn)制數(shù)。兩者差了二十多個(gè)數(shù)量級(jí)用long long存這個(gè)答案連中間過程都走不完第一次乘法就會(huì)溢出成負(fù)數(shù)或者垃圾值。4.2 C 手寫大數(shù)乘法與比較的骨架C 沒有任何內(nèi)置大數(shù)必須手寫。好在這道題只需要兩個(gè)操作大數(shù)乘大數(shù)和大數(shù)比較大數(shù)。我一般用低位在前的數(shù)組存十進(jìn)制位也就是d[0]存?zhèn)€位d[1]存十位以此類推。這樣進(jìn)位的時(shí)候從下標(biāo) 0 往大走寫起來最順手。大數(shù)比較的邏輯很簡(jiǎn)單先比位數(shù)位數(shù)多的更大位數(shù)相同就從高位往低位逐位比第一位不同的誰(shuí)大誰(shuí)就大。這里有個(gè)非常經(jīng)典的錯(cuò)誤就是只寫位數(shù)不同時(shí)比位數(shù)位數(shù)相同就返回相等——位數(shù)相同但數(shù)值不同的情況多了去了比如 1234 和 4321 都是 4 位必須逐位比較才能分出大小。大數(shù)乘法的核心是模擬豎式兩層循環(huán)把d[i] * d[j]累加到結(jié)果的第ij位上等所有位都累加完再?gòu)牡臀坏礁呶唤y(tǒng)一處理進(jìn)位。中間累加用的數(shù)組要開得足夠大長(zhǎng)度份應(yīng)該是兩個(gè)乘數(shù)位數(shù)之和再加 2。關(guān)于中間值會(huì)不會(huì)溢出這里可以放心每一位的乘積最大是 9 × 9 81而同一位置上最多累加 40 次也就是 3240 左右int完全裝得下。所以中間數(shù)組用int就夠不需要long long。從字符串轉(zhuǎn)大數(shù)也有個(gè)小講究。我習(xí)慣用逐位乘 10 加當(dāng)前位的方式從左到右掃字符串每讀一位就把當(dāng)前大數(shù)整體乘 10 再加上這一位的數(shù)字。這個(gè)過程中要用一個(gè)carry變量從低位往高位傳遞邏輯和乘法進(jìn)位一樣。特別注意全為 0 的輸入因?yàn)?0 乘 10 還是 0沒有產(chǎn)生任何進(jìn)位數(shù)組長(zhǎng)度會(huì)一直是 0必須特判——如果掃完了長(zhǎng)度還是 0就把值設(shè)成 0、長(zhǎng)度設(shè)成 1。4.3 Python 與 Java 的降維寫法如果你只是想把這道題的思路搞明白而不是非得在 C 里手寫高精度那用 Python 寫這道題簡(jiǎn)直是降維打擊。Python 的整數(shù)是任意精度的int直接就能存 40 位、甚至 1000 位的數(shù)乘法和比較都是原生支持的。同樣一段 DP 邏輯Python 版本連大數(shù)類都不用寫字符串轉(zhuǎn)整數(shù)直接int(s[i-1:j])搞定十幾行代碼就能 AC。Java 的話java.math.BigInteger提供了multiply和compareTo兩個(gè)方法也能省掉手寫高精度的功夫只是寫起來比 Python 啰嗦一些。不過我還是建議你至少手寫一遍 C 版本。原因很現(xiàn)實(shí)競(jìng)賽的默認(rèn)語(yǔ)言還是 C遇到真正卡高精度的題目你總得會(huì)寫。Python 版本適合用來驗(yàn)證你的 DP 邏輯對(duì)不對(duì)——如果 Python 過了而 C 不過那問題一定出在高精度實(shí)現(xiàn)上排查方向一下子就清晰了。這里補(bǔ)充一句復(fù)雜度分析方便你判斷自己的實(shí)現(xiàn)會(huì)不會(huì)超時(shí)。整個(gè) DP 的乘法調(diào)用次數(shù)約為 K × N2 / 2在 K 6、N 40 時(shí)大約是 4800 次每次大數(shù)乘法是 O(L2)L 最多 80 位左右也就是幾千次基本運(yùn)算。乘起來大概三千多萬(wàn)次基本操作在 C 里是毫秒級(jí)的完全不用擔(dān)心性能。5. 完整代碼與調(diào)試現(xiàn)場(chǎng)我在下標(biāo)上栽的三個(gè)跟頭代碼我給兩個(gè)版本C 的手寫高精度版和 Python 的直球版。給完之后重點(diǎn)說說我當(dāng)年調(diào)試時(shí)踩過的坑這幾處比代碼本身更值錢。5.1 C 版本數(shù)組存大數(shù) 手寫乘法#include bits/stdc.h using namespace std; const int MAXL 105; struct Big { int d[MAXL]; // d[0] 是個(gè)位下標(biāo)越大位權(quán)越高 int len; Big() { memset(d, 0, sizeof(d)); len 1; } // 默認(rèn)值是 0 }; // 把 s[l..r] 轉(zhuǎn)成大數(shù)下標(biāo)從 0 開始閉區(qū)間 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 當(dāng)前位 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]這個(gè)下標(biāo)最容易看暈dp里用的是前 i 位這種 1 起始的計(jì)數(shù)而num數(shù)組和字符串都是 0 起始的。前 i 位對(duì)應(yīng)字符串下標(biāo)0..i-1前 t 位對(duì)應(yīng)0..t-1所以最后一段就是從下標(biāo) t 到 i-1寫成num[t][i-1]。這個(gè)問題我在下一節(jié)會(huì)專門說。5.2 Python 版本n, k map(int, input().split()) s input().strip() # num[i][j]第 i 位到第 j 位組成的整數(shù)1 起始的閉區(qū)間 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])兩邊對(duì)照著看能明顯感覺到 Python 把所有高精度的臟活都藏起來了剩下的骨架跟 C 一模一樣。建議你先用 Python 把邏輯跑通再用 C 重寫一遍這樣調(diào)試的時(shí)候能確定問題到底是出在算法還是出在高精度實(shí)現(xiàn)上。5.3 三個(gè)真實(shí)踩坑記錄坑一num 數(shù)組的下標(biāo)基準(zhǔn)混用。我當(dāng)初寫 C 版本的時(shí)候dp用的是 1 起始前 i 位結(jié)果在取最后一段的時(shí)候順手寫成了num[t 1][i]按照 Python 那套 1 起始的約定來寫的。但 C 里num存的是 0 起始的字符串切片num[t1][i]實(shí)際取到的是從下標(biāo) t1 到 i 的內(nèi)容正好錯(cuò)開了一位。表現(xiàn)就是樣例能過因?yàn)槲粩?shù)少錯(cuò)位不太明顯但交上去大面積 WA。這種錯(cuò)誤的排查方法很簡(jiǎn)單打印中間狀態(tài)把所有dp[i][0]打出來跟手算的前綴數(shù)值對(duì)一下一眼就能看出來錯(cuò)位?？佣髷?shù)比較只比長(zhǎng)度。這是我見過最高頻的高精度錯(cuò)誤。很多人寫比較函數(shù)的時(shí)候圖省事只寫了if (a.len ! b.len) return a.len b.len; return false;長(zhǎng)度相同就直接認(rèn)為相等。這在本題里會(huì)直接導(dǎo)致答案偏小因?yàn)閮蓚€(gè)位數(shù)相同的候選乘積會(huì)互相頂?shù)糇詈罅粝碌目赡懿皇钦嬲畲蟮哪莻€(gè)。正確寫法必須是長(zhǎng)度相同時(shí)逐位從高位往下比?？尤朔ㄖ虚g數(shù)組沒清空、或者開小了。中間數(shù)組tmp每次調(diào)用乘法都要重新清零如果把它寫成全局變量或者static上一次的結(jié)果會(huì)殘留下來污染這一次的計(jì)算。另外數(shù)組長(zhǎng)度也要留夠兩個(gè) 40 位大數(shù)相乘結(jié)果最多 80 位進(jìn)位之后可能到 81 位所以我習(xí)慣開MAXL * 2也就是 210穩(wěn)一點(diǎn)。還有一個(gè)不算坑但值得提的點(diǎn)輸出大數(shù)的時(shí)候千萬(wàn)別忘了逆序。因?yàn)閿?shù)組是低位在前的d[0]是個(gè)位輸出必須從len-1往下走到 0。寫成從 0 到len-1輸出的話你會(huì)看到一個(gè)數(shù)字完全反過來的答案。6. 換個(gè)問法這道題還能怎么變形把這道題的正解寫出來只是第一步。真正讓這道題的價(jià)值翻倍的是它背后那一套區(qū)間分割 決策枚舉的思維能直接遷移到一大批變體上。這里挑幾個(gè)最有代表性的說說。6.1 至多 K 個(gè)乘號(hào)多一層取 max 就夠如果題目改成至多使用 K 個(gè)乘號(hào)答案就不是dp[n][K]了而是max(dp[n][0], dp[n][1], ..., dp[n][K])。為什么因?yàn)槎嘤靡粋€(gè)乘號(hào)并不總是更好。舉個(gè)極端的例子數(shù)字串10、K 1切一刀得到1 * 0 0不切得到10。顯然不切更優(yōu)。原因是數(shù)字串里出現(xiàn)了 0任何跟 0 相乘的段都會(huì)把整個(gè)乘積拉成 0。所以遇到至多這種表述最后答案要在一個(gè)維度上再掃一遍取最大值。這個(gè)改動(dòng)只有幾行但如果不注意題目到底是恰好還是至多就會(huì)直接 WA。6.2 要求輸出切分方案加一個(gè)決策點(diǎn)數(shù)組有些變體會(huì)要求你不只輸出最大乘積還要輸出具體的切分方式比如在第幾位后面插乘號(hào)。這時(shí)候只需要在原來的轉(zhuǎn)移里多記一個(gè)數(shù)組pre[i][j]表示計(jì)算dp[i][j]時(shí)選中的那個(gè)最優(yōu) t 是多少。轉(zhuǎn)移的時(shí)候只要發(fā)現(xiàn)當(dāng)前候選值比dp[i][j]大就順手把pre[i][j] t記下來。最后從pre[n][K]出發(fā)往前回溯記t pre[n][K]那么最后一個(gè)乘號(hào)插在第 t 位后面接著跳到狀態(tài)dp[t][K-1]取pre[t][K-1]以此類推直到乘號(hào)用完?；厮莩鰜淼奈恢眯蛄蟹催^來輸出就是完整的切分方案。這個(gè)技巧的通用性極強(qiáng)幾乎所有輸出方案的 DP 題都是這個(gè)套路多開一個(gè)數(shù)組記錄我是從哪個(gè)狀態(tài)轉(zhuǎn)移過來的。6.3 和石子合并矩陣連乘的家族關(guān)系如果你做過經(jīng)典的石子合并或者矩陣連乘應(yīng)該會(huì)有種熟悉感。那類題的狀態(tài)是f[i][j]表示把第 i 堆到第 j 堆合并成一堆的最小代價(jià)枚舉的是最后一次合并的分界點(diǎn) k轉(zhuǎn)移形如f[i][j] min(f[i][k] f[k1][j] 代價(jià))。乘積最大這道題的結(jié)構(gòu)其實(shí)是一樣的枚舉最后一段的起點(diǎn)只不過這道題的左半部分是從串首開始的前綴而不是任意區(qū)間。之所以有區(qū)別是因?yàn)槭雍喜⒁喜⒊梢粋€(gè)整體所以左右兩部分都是中間區(qū)間的形式而乘積最大的最終結(jié)果是一條從前到后的完整劃分所以左邊的狀態(tài)天然就是前綴。理解了這個(gè)同構(gòu)關(guān)系你會(huì)發(fā)現(xiàn)一大類題都能用同一套思考框架去套確定決策動(dòng)作 → 確定狀態(tài)維度 → 推出轉(zhuǎn)移時(shí)枚舉的分界點(diǎn) → 確定邊界和初始化 → 處理數(shù)值溢出和精度。這套流程走順了區(qū)間 DP 這一類題基本就通了。我個(gè)人在實(shí)際刷題過程中的體會(huì)是像 1275 這種看起來簡(jiǎn)單的老題其實(shí)是最值得反復(fù)琢磨的。它把狀態(tài)定義枚舉邊界高精度這三個(gè)動(dòng)態(tài)規(guī)劃的核心考點(diǎn)全揉在一起了每一處都能踩坑每一處也都能學(xué)到東西。第一次寫不出來很正常把樣例的那張 DP 表親手推兩遍再對(duì)著代碼單步走一遍這道題就真正變成你自己的了。