[noip2000]乘积最大

形式化题目

给定一个长度为 $N$ 的数字串 $s$ 和自然数 $K$ 。在 $s$ 的 $N-1$ 个字符间隙中选出 $K$ 个插入乘号，把数字串分成 $K+1$ 段，每段看作一个十进制整数。求这些整数的乘积的最大值。

题面样例： $s = 312$ ， $K = 1$ 时有 3*12=36 和 31*2=62 两种分法，最大值为 $62$ 。

正解

思路

朴素做法：枚举 $K$ 个乘号放在哪 $K$ 个间隙里，共有 $\binom{N-1}{K}$ 种方案（ $N=40, K=6$ 时约 $3.3 \times 10^6$ 种），逐一切分、连乘、取最大。慢的根源不是方案数太大，而是子问题被大量重复计算——只要前 $t$ 个字符之间的乘号位置相同，"前 $t$ 位能取得的最大乘积"就是同一个值，与后面的划分无关。

优化推导：把这部分公共子问题提出来，定义

dp[j][i] = \text{前 } i \text{ 个数字之间插入 } j \text{ 个乘号的最大乘积}

对"最后一个乘号放在哪"做决策：设它放在位置 $t$ 之后，则前缀被切成两半——前 $t$ 位内部放 $j-1$ 个乘号，第 $t+1 \sim i$ 位自成一段（不再含乘号）。于是

dp[j][i] = \max_{j \leqslant t < i} \; dp[j-1][t] \times \text{num}(t+1,\, i)

两个下界 $t \geqslant j$ 与 $t < i$ 分别来自"每段至少 1 位"：前 $t$ 位要放得下 $j-1$ 个乘号，末段不能为空。这个转移成立依赖两个经典性质：

最优子结构：若最优方案中最后一个乘号在 $t$ 之后，而前 $t$ 位内部的放法不是最优，换成更优放法只会让总乘积更大（各段值均为正整数），矛盾；
无后效性： $dp[j-1][t]$ 只由"前 $t$ 位、 $j-1$ 个乘号"决定，末段取值与前缀内部怎么分无关。

边界： $dp[0][i] = \text{num}(1, i)$ ，即不放乘号时整个前缀自己就是一个数。答案为 $dp[K][N]$ 。

还有一个本题特有的便利： $N \leqslant 40$ ，乘积最多约 $10^{40}$ ，早超出了 64 位整数范围——C++ 需要高精度乘法，而 Python 的 int 天然支持任意精度，直接乘即可。

样例 DP 表： $s = 1231$ 、 $K = 2$ （题面样例的扩展）。行为乘号数 $j$ ，列为前缀长度 $i$ ；单元格是 $dp[j][i]$ ，— 表示前 $i$ 位放不下 $j$ 个乘号（ $i < j+1$ ）。

$dp[j][i]$	$i=1$	$i=2$	$i=3$	$i=4$
$j=0$	1	12	123	1231
$j=1$	—	2	36	372
$j=2$	—	—	—	62

看一轮具体转移： $j=1$ 行的 $dp[1][3] = \max(dp[0][1] \times 23,\; dp[0][2] \times 3) = \max(23, 36) = 36$ ； $dp[1][4] = \max(1 \times 231,\; 12 \times 31,\; 123 \times 1) = 372$ ——注意它不是 $231$ ：把前两位留成一段 12 再乘 31 更划算。最后一格 $dp[2][4]$ 枚举最后一个乘号的位置 $t \in \{2, 3\}$ ： $dp[1][2] \times 31 = 2 \times 31 = 62$ ， $dp[1][3] \times 1 = 36$ ，取最大得 $62$ ，与题面样例的 31*2=62（同一乘积的镜像切分）一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 十进制大整数（little-endian），只做本题需要的加法/乘法/比较
struct BigInt {
    vector<int> d;
    BigInt() { d.push_back(0); }
    BigInt(ll x) { d.clear(); if (x == 0) d.push_back(0); else while (x) { d.push_back(x % 10); x /= 10; } }
    BigInt(const string& s) { d.clear(); for (int i = (int)s.size() - 1; i >= 0; i--) d.push_back(s[i] - '0'); if (d.empty()) d.push_back(0); trim(); }
    void trim() { while (d.size() > 1 && d.back() == 0) d.pop_back(); }
    bool is_zero() const { return d.size() == 1 && d[0] == 0; }
    int cmp(const BigInt& o) const {
        if (d.size() != o.d.size()) return d.size() < o.d.size() ? -1 : 1;
        for (int i = (int)d.size() - 1; i >= 0; i--)
            if (d[i] != o.d[i]) return d[i] < o.d[i] ? -1 : 1;
        return 0;
    }
    bool operator<(const BigInt& o) const { return cmp(o) < 0; }
    string str() const { string r; for (int i = (int)d.size() - 1; i >= 0; i--) r += char('0' + d[i]); return r; }

    BigInt operator*(const BigInt& o) const {
        BigInt r; r.d.assign(d.size() + o.d.size(), 0);
        for (size_t i = 0; i < d.size(); i++)
            for (size_t j = 0; j < o.d.size(); j++)
                r.d[i + j] += d[i] * o.d[j];
        for (size_t i = 0; i + 1 < r.d.size(); i++) { r.d[i + 1] += r.d[i] / 10; r.d[i] %= 10; }
        r.trim(); return r;
    }
};

int n, k;
string s;
BigInt dp[8][45];   // dp[j][i]：前 i 个数字插 j 个乘号的最大乘积

BigInt substr_num(int l, int r) {   // s[l..r) 的数字（0 基，r 不含）
    return BigInt(s.substr(l, r - l));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> s;
    for (int i = 1; i <= n; i++)
        dp[0][i] = substr_num(0, i);
    for (int j = 1; j <= k; j++) {
        for (int i = j + 1; i <= n; i++) {
            BigInt best(0);
            for (int t = j; t < i; t++) {
                BigInt cand = dp[j - 1][t] * substr_num(t, i);
                if (best < cand) best = cand;
            }
            dp[j][i] = best;
        }
    }
    cout << dp[k][n].str() << "\n";
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 03:23
# update_at: 2026-10-02 03:23

import sys


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    k = int(next(data))
    s = next(data).decode()

    # dp[j][i]：前 i 个数字之间插 j 个乘号能得到的最大乘积
    dp: list[list[int]] = [[0] * (n + 1) for _ in range(k + 1)]
    dp[0] = [0] + [int(s[:i]) for i in range(1, n + 1)]  # 不放乘号：整个前缀自己就是一个数

    for j in range(1, k + 1):
        # 枚举最后一个乘号的位置：插在第 t 位后面，前 t 位放 j-1 个乘号，s[t:i] 自成一段
        for i in range(j + 1, n + 1):
            dp[j][i] = max(dp[j - 1][t] * int(s[t:i]) for t in range(j, i))

    print(dp[k][n])


if __name__ == "__main__":
    solve()

复杂度

时间：状态 $O(KN)$ 个，每个转移枚举 $O(N)$ 个位置，总转移 $O(KN^2) \leqslant 6 \times 40^2 = 9600$ 次，每次含一次不超过 $10^{40}$ 的大整数乘法（Python 原生支持，成本可忽略）。实测 10 组官方数据每组约 17ms。
空间： $dp$ 表 $O(KN)$ 。

朴素枚举则需要约 $3.3 \times 10^6$ 个方案、每方案再做 $K$ 次大数乘法，DP 比它低了两个数量级以上。

总结

本题是经典的"数字串插乘号"区间划分 DP：状态 $dp[j][i]$ 表示"前 $i$ 位放 $j$ 个乘号的最大乘积"，转移枚举最后一个乘号的位置。关键点有三：一是发现朴素枚举的重复子问题，引出按"乘号数 × 前缀长度"分层的 DP；二是转移下界 $t \geqslant j$ 由"每段至少 1 位"推出；三是 $N \leqslant 40$ 导致乘积达 $10^{40}$ 量级，C++ 需高精度而 Python 直接用大整数。

目录

形式化题目

正解

思路

代码

复杂度

总结