切割相加 題解｜APCS 2026 年 11 月高級 第 3 題

前置知識

這題是「切成好幾段、總和有上限」的計數 DP，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 用整數的位元枚舉子集（子題組 1 用）：NTUCPC Guide〈枚舉〉的「集合」一節——\(n\) 個東西的每一種「選或不選」對應 \(0\) 到 \(2^n - 1\) 的一個整數，第 \(i\) 個 bit 代表第 \(i\) 個選了沒；吳邦一《AP325》第 1 章的 P-1-7「子集合乘積」用迴圈和遞迴各窮舉一次（教材 PDF 第 27～28 頁；Python 版第 1 章；站上題目 ap325p107）。會用到 >>、& 這兩個位元運算子。
• DP 的狀態與轉移：NTUCPC Guide〈狀態與轉移〉——狀態、轉移、初始狀態，時間＝狀態數 × 每個狀態的轉移時間；數方法數的題目，轉移用加法。《AP325》第 6 章 6.1 講同一套（教材 PDF 第 161～167 頁；Python 版第 6 章（I））。
• 把「總和」放進狀態：NTUCPC Guide〈背包問題〉——01 背包把「目前的總重量」當成第二個維度，重量上限不大就算得完；《AP325》P-6-9「大賣場免費大搬家」也是加上「重量」這第二個條件（教材 PDF 第 180～182 頁；Python 版第 6 章（II）；站上題目 ap325p609）。本題要帶走的是：總和有上限 \(m\)、而 \(m\) 不大，就把總和放進狀態。
• 整數溢位：語法書 2.9——int 大約只到 \(2 \times 10^9\)、long long 大約到 \(9 \times 10^{18}\)，算出來的數超過就會溢位。

簡潔題意

給一個只由數字 \(1\)～\(9\) 組成的字串 \(S\)，長度記為 \(n\)（題目寫成 \(|S|\)）。在相鄰兩個數字之間的 \(n - 1\) 個空隙裡挑一些插入加號（一個都不插也算一種插法），變成一個加法算式。在所有結果不超過 \(m\) 的插法中，求最大的結果，以及結果剛好等於它的插法有幾種（\(1 \le n \le 40\)，\(1 \le m \le 3 \times 10^4\)，\(m\) 不小於 \(S\) 的數字總和，答案的插法數不超過 \(2^{31} - 1\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(40\) 分）：\(n \le 18\)。
• 子題組 2（\(60\) 分）：無額外限制。

先拿下 40 分：每個空隙插或不插，全部試一遍

\(n - 1\) 個空隙各自插或不插，插法一共 \(2^{n-1}\) 種；\(n \le 18\) 時最多 \(2^{17} = 131072\) 種，一種一種算出結果就好。

用一個整數 mask 代表一種插法：第 \(i\) 個 bit 是 \(1\)，代表 s[i] 和 s[i + 1] 之間插了加號。例如範例 1 的 36+3+1+9，加號在 s[1]、s[2]、s[3] 後面，mask 就是 \(2^1 + 2^2 + 2^3 = 14\)。mask 從 \(0\) 開始試——\(0\) 就是一個加號都不插的那一種。

每個 mask 從左到右掃一遍：把 s[i] 接到目前這一段的尾巴（cur = cur * 10 + 數字）；s[i] 後面有加號、或已經是最後一個數字，這一段就結束，加進總和。總和不超過 \(m\) 的，用擂台記下最大值和它出現幾次。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int m;
    cin >> s >> m;
    int n = s.size();

    long long best = -1, cnt = 0;                    // 最大的結果、出現幾次
    for (long long mask = 0; mask < (1LL << (n - 1)); mask++) {   // 第 i 個 bit 是 1：s[i] 後面插加號
        long long sum = 0, cur = 0;                  // 一段最長 18 位，int 裝不下
        for (int i = 0; i < n; i++) {
            cur = cur * 10 + (s[i] - '0');           // 把 s[i] 接到這一段的尾巴
            if (i == n - 1 || ((mask >> i) & 1)) {   // 這一段到 s[i] 結束
                sum += cur;
                cur = 0;
            }
        }
        if (sum <= m) {
            if (sum > best) {
                best = sum;
                cnt = 1;
            } else if (sum == best) {
                cnt++;
            }
        }
    }
    cout << best << '\n' << cnt << '\n';
    return 0;
}

cur 和 sum 要用 long long：一個加號都不插時，整串就是一段，\(18\) 個 \(9\) 大約是 \(10^{18}\)。int 的上限大約是 \(2 \times 10^9\)，十位數就可能溢位；long long 大約到 \(9.2 \times 10^{18}\)，\(18\) 位數全部裝得下，\(19\) 個 \(9\) 就裝不下了——子題組 1 的 \(n \le 18\) 正好卡在這裡。把一段拆成兩段只會讓值變小，所以總和不會比整串的值大，sum 也裝得下。

本站實測 \(n = 18\) 約 \(0.01\) 秒，子題組 1 的 \(40\) 分穩穩到手。\(n = 40\) 時插法有 \(2^{39} \approx 5.5 \times 10^{11}\) 種，怎麼樣都跑不完——要換個做法。

從 40 分到 100 分：把「總和」放進狀態

先看兩件事：

• 每一段最多 \(5\) 位：每個數字至少是 \(1\)，\(6\) 位數的段至少是 \(111111\)，已經超過 \(3 \times 10^4 \ge m\)——用到這種段的插法結果一定超過 \(m\)，不必考慮。
• 總和只要記 \(0\)～\(m\)：超過 \(m\) 的插法不要，而 \(m \le 3 \times 10^4\) 不大，可以把「目前的總和」放進狀態。

\(dp[i][t]\) ＝ 把 \(S\) 的前 \(i\) 個數字切成一段一段、各段加起來恰好是 \(t\) 的插法數（\(0 \le t \le m\)）。

初始值是 \(dp[0][0] = 1\)：一個數字都還沒切，總和是 \(0\)，只有一種。

轉移：前 \(j\) 個數字已經切完、總和是 \(t\)；下一段從 s[j] 開始、到 s[k] 結束，值是 \(v\)。只要 \(t + v \le m\)，就變成「前 \(k + 1\) 個數字切完、總和 \(t + v\)」：

\(v\) 從 s[j] 開始一位一位往右接，一超過 \(m\) 就停——再往右接只會更大。這個 break 同時保證一段最長 \(5\) 位（第 \(6\) 位一定超過 \(m\)），\(v\) 也最多算到 \(10m + 9\)、不會溢位。\(j\) 由小到大處理：每一段都從比它的終點小的位置出發，輪到 \(j\) 時，所有結束在 \(j\) 的段都已經加過來了，\(dp[j]\) 不會再變。

全部 \(n\) 個數字都切完的那一列 \(dp[n]\)，從 \(t = m\) 往下找第一個不是 \(0\) 的格子：\(t\) 就是最大的結果，\(dp[n][t]\) 就是插法數。題目保證 \(m\) 不小於數字總和，「全部拆開」那種插法的結果正是數字總和，所以一定找得到。

範例 2 的整張表就是圖 1：橫軸是 \(i\)、縱軸是總和 \(t\)，每個圓圈是一格不是 \(0\) 的 \(dp[i][t]\)，圈裡是插法數。一種插法就是一條從 \(dp[0][0]\) 出發、一段一段往右上走的路：往右走「這一段的位數」（兩位數的段跨兩欄，畫成弧線），往上走「這一段的值」，超過 \(m = 100\) 的路一律不要。最後一欄從 \(100\) 往下找，\(94\)～\(100\) 都是 \(0\)，第一個是 \(dp[8][93] = 2\)——題目敘述舉的那兩種插法，就是圖上兩條彩色的路。

\(dp[8][93]\) 這一格怎麼來的？看最後一段：

• 7：從 \(dp[7][86] = 1\) 接過來；
• 17：從 \(dp[6][76] = 1\) 接過來；
• 217 已經超過 \(m\)，接不了。

所以 \(dp[8][93] = 1 + 1 = 2\)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int m;
    cin >> s >> m;
    int n = s.size();

    // dp[i][t]：前 i 個數字切完、總和恰好是 t 的插法數
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    dp[0][0] = 1;                                    // 還沒切任何數字：總和 0，一種
    for (int j = 0; j < n; j++) {                    // 下一段從 s[j] 開始
        int v = 0;
        for (int k = j; k < n; k++) {                // 這一段是 s[j]～s[k]
            v = v * 10 + (s[k] - '0');
            if (v > m) break;                        // 再往右接只會更大
            for (int t = 0; t + v <= m; t++)
                dp[k + 1][t + v] += dp[j][t];
        }
    }

    for (int t = m; t >= 0; t--) {                   // 從 m 往下找第一個做得到的總和
        if (dp[n][t] > 0) {
            cout << t << '\n' << dp[n][t] << '\n';
            break;
        }
    }
    return 0;
}

時間：每個起點最多接 \(5\) 位就停，每接一位就把 \(t\) 從 \(0\) 掃到 \(m\)，一共 \(O(n \cdot 5 \cdot m)\)，最多約 \(6 \times 10^6\) 次加法，本站實測 \(n = 40\)、\(m = 30000\) 不到 \(0.02\) 秒。記憶體：表格 \(41 \times 30001\) 格 long long，約 \(10\) MB。

表格存的是插法數，要用 long long：前 \(i\) 個數字的插法一共 \(2^{i-1}\) 種，一格最多 \(2^{39} \approx 5.5 \times 10^{11}\)，long long 裝得下。題目只保證答案那一格不超過 \(2^{31} - 1\)，其他格子可以更大——\(40\) 個 \(1\) 時，總和 \(1534\) 那一格有 \(3294910080\) 種，int 裝不下。

測過再交：範例的最大值都碰不到 \(m\)

兩個範例的最大值都比 \(m\) 小（\(49 < 50\)、\(93 < 100\)），答案裡的段最長只有兩位數，平手也都只有 \(2\) 種。沒蓋到的：結果剛好等於 \(m\)、只有一個數字、\(m\) 剛好是數字總和、不插加號最好、平手很多、段值超過 int、最長的字串。

七筆都親眼看過正確，這題就穩了。