【例9.19】乘积最大

题目描述

设有长度为 N 的数字串，用 K 个乘号切成 K+1 段（允许前导零），使各段整数乘积最大。第一行 N, K（6 ≤ N ≤ 10，1 ≤ K ≤ 6），第二行数字串；输出最大乘积。

样例：N=4, K=2，串 1231 → 输出 62。

思路

区间 DP：设 dp[i] 为前 i 位用当前刀数切出的最大乘积，按刀数逐层滚动更新，每层枚举最后一刀位置 t，转移 dp[i] = max(dp[t] * val(t, i))，答案为 dp[N]。

参考代码

Python 版：

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
31#!/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-09-30 02:51
# update_at: 2026-10-09 14:25

import sys


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))  # n 位数字
    k = int(next(data))  # 切 k 刀
    s = next(data).decode()  # 数字串本身是字符串，不能进 map(int)，否则丢前导 0

    # dp[i]：前 i 位数字用掉当前刀数后能得到的最大乘积
    dp = [0] + [int(s[:i]) for i in range(1, n + 1)]  # 0 刀时整段就是一个因子

    for j in range(1, k + 1):  # 逐刀加入，第 j 层复用第 j-1 层的结果
        # 最后一刀落在第 t 位之后：左半段是上一层的 dp[t]，右半段是子串 s[t:i]
        dp = [
            max((dp[t] * int(s[t:i]) for t in range(j, i)), default=0)
            for i in range(n + 1)
        ]

    print(dp[n])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-04 14:30
 * update_at: 2026-10-05 07:45
 */
// main.cpp：把长度为 N 的数字串插入 K 个乘号切成 K+1 段，使各段整数乘积最大。
// DP：dp[i] 表示前 i 位用当前刀数能得到的最大乘积，逐层滚动枚举最后一刀位置 t。

#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 15;

int n, k;
char s[MAXN];
ll dp[MAXN]; // dp[i]：前 i 位用掉当前层刀数后的最大乘积

// 子串 [l, r) 的十进制值（l 从 0 起，半开区间），允许前导 0。
ll val(int l, int r) {
    ll v = 0;
    for (int i = l; i < r; i++) {
        v = v * 10 + (s[i] - '0');
    }
    return v;
}

void solve() {
    // 0 刀时整段就是一个因子
    for (int i = 1; i <= n; i++) {
        dp[i] = val(0, i);
    }
    dp[0] = 0;

    // 逐层加入第 j 把刀，第 j 层只依赖第 j-1 层的 dp
    for (int j = 1; j <= k; j++) {
        ll pre[MAXN];
        for (int i = 0; i <= n; i++) pre[i] = dp[i]; // 暂存上一层结果

        for (int i = 1; i <= n; i++) {
            ll best = 0;
            // 最后一刀落在第 t 位之后，左半段长 j 位是下限
            for (int t = j; t <= i - 1; t++) {
                ll cur = pre[t] * val(t, i);
                if (cur > best) best = cur;
            }
            dp[i] = best;
        }
    }

    printf("%lld\n", dp[n]);
}

int main() {
    // 输入：第一行 N K，第二行是长度为 N 的数字串
    scanf("%d %d", &n, &k);
    scanf("%s", s);
    solve();
    return 0;
}

【例9.19】乘积最大

目录

题目描述

思路

参考代码