算式

GitHub跳转原题关系图返回列表

设 dp[l][r][t] 表示区间内恰好用 t 个乘号的最大值，转移时枚举最后一次运算是加号还是乘号。

OJ: luogu

题目 ID: P1388

难度:普及/提高-

标签:动态规划区间dp推导

日期: 2026-06-19 12:14

目录

  1. 题意
  2. 思路
    1. 1. 不放乘号
    2. 2. 最后一次运算是加号
    3. 3. 最后一次运算是乘号
    4. 状态表示例
    5. DP 公式
  3. 代码
  4. 复杂度
  5. 总结

题意

给出 n 个数字，顺序不能改变。

要求在中间恰好加入 k 个乘号，其余位置放加号，并且允许任意加括号，使最终表达式的值最大。

思路

先看一个容易误判的点：本题不能简单理解成“把序列切成 k+1 段，每段求和后相乘”。

反例是：

text
n = 3, k = 1
0 0 1

如果只按“段和相乘”，无论切成 (0) × (0+1) 还是 (0+0) × (1)，结果都是 0。 但合法表达式可以是：

text
(0 × 0) + 1 = 1

所以真正需要考虑的是：任意加括号后，整个区间的最后一次运算可能是加号，也可能是乘号。

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：小数据暴力解，递归枚举最后一次运算和左右乘号数量。

const int MAXN = 20;

int n, k;
int a[MAXN];
int sum[MAXN];

int range_sum(int l, int r) {
    return sum[r] - sum[l - 1];
}

long long solve(int l, int r, int t) {
    if (t < 0 || t > r - l) {
        return -1;
    }
    if (t == 0) {
        return range_sum(l, r);
    }

    long long best = -1;

    for (int mid = l; mid < r; mid++) {
        int left_len = mid - l + 1;
        int right_len = r - mid;

        // 最后一次运算是加号：左右乘号数量之和为 t。
        for (int x = 0; x <= t; x++) {
            int y = t - x;
            if (x >= left_len || y >= right_len) {
                continue;
            }
            long long left_value = solve(l, mid, x);
            long long right_value = solve(mid + 1, r, y);
            if (left_value == -1 || right_value == -1) {
                continue;
            }
            best = max(best, left_value + right_value);
        }

        // 最后一次运算是乘号：当前这个乘号占 1 个。
        for (int x = 0; x <= t - 1; x++) {
            int y = t - 1 - x;
            if (x >= left_len || y >= right_len) {
                continue;
            }
            long long left_value = solve(l, mid, x);
            long long right_value = solve(mid + 1, r, y);
            if (left_value == -1 || right_value == -1) {
                continue;
            }
            best = max(best, left_value * right_value);
        }
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    cout << solve(1, n, k) << '\n';
    return 0;
}

brute.cpp 直接用递归表示：

solve(l, r, t) = 区间 [l,r] 内恰好放 t 个乘号时的最大值

如果 t=0t = 0，说明整段只能全加，答案就是区间和。 否则，最后一次运算会把区间拆成左右两部分：

  • 如果最后一次运算是加号，左右两边的乘号数量之和为 t；
  • 如果最后一次运算是乘号，当前这个乘号占掉 1 个，左右两边的乘号数量之和为 t-1。

这个想法已经很接近正解了，问题只在于会重复计算同一个区间。

于是直接改成区间 DP：

设：

dp[l][r][t] = 区间 [l,r] 内恰好放 t 个乘号时的最大值

1. 不放乘号

如果 t=0t = 0，整段只能全加：

dp[l][r][0] = sum(l, r)

这里用前缀和 sum 就能 O(1)O(1) 求出区间和。

2. 最后一次运算是加号

如果最后一次运算把区间拆成 [l, mid] 和 [mid+1, r]，并且这个运算是加号。

假设左边用了 x 个乘号，那么右边就用了 t-x 个乘号。

转移为：

dp[l][r][t] = max(dp[l][mid][x] + dp[mid+1][r][t-x])

3. 最后一次运算是乘号

如果最后一次运算是乘号，那么当前这个乘号本身就占掉 1 个。

假设左边用了 x 个乘号，那么右边就用了 t-1-x 个乘号。

转移为：

dp[l][r][t] = max(dp[l][mid][x] * dp[mid+1][r][t-1-x])

两个转移都要枚举所有合法的 mid 和 x。

实现时建议用 long long 保存 DP 值。题面保证最终答案小于 2312^31，但中间区间状态不一定值得冒溢出的风险。

状态表示例

样例是：

1 2 3 4 5，k=2k = 2

几个关键状态如下：

状态 值 说明
dp[1][5][0] 15 全部做加法
dp[1][3][1] 9 1 × (2+3) 或 (1+2) × 3
dp[1][3][2] 6 1 × 2 × 3
dp[4][5][0] 9 4 + 5
dp[1][5][2] 120 最优值可以由 (1+2+3) × 4 × 5 得到

因此最终答案是 120。

DP 公式

设 sum(l,r)sum(l,r) 表示区间 [l,r][l,r] 的数字和，dpl,r,tdp_{l,r,t} 表示在区间 [l,r][l,r] 内恰好放 tt 个乘号时的最大值。没有乘号时：

dpl,r,0=sum(l,r) dp_{l,r,0}=sum(l,r)

若最后一次运算是加号：

dpl,r,t=max⁡mid,x(dpl,mid,x+dpmid+1,r,t−x) dp_{l,r,t}=\max_{mid,x}\left(dp_{l,mid,x}+dp_{mid+1,r,t-x}\right)

若最后一次运算是乘号：

dpl,r,t=max⁡mid,x(dpl,mid,x⋅dpmid+1,r,t−1−x) dp_{l,r,t}=\max_{mid,x}\left(dp_{l,mid,x}\cdot dp_{mid+1,r,t-1-x}\right)

最终答案为：

dp1,n,k dp_{1,n,k}

公式解释：没有乘号时整段只能做加法，所以是区间和。若区间中有乘号，最后一次运算可能是加号也可能是乘号，分别枚举切点和左右乘号数量分配，就能覆盖所有括号方案。

代码

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

const int MAXN = 20;

int n, k;
int a[MAXN];
int sum[MAXN];
long long dp[MAXN][MAXN][MAXN];

int range_sum(int l, int r) {
    return sum[r] - sum[l - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    memset(dp, -1, sizeof(dp));

    // dp[l][r][t] 表示区间 [l,r] 内恰好放 t 个乘号时的最大值。
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            // 不放乘号时，整个区间只能全部用加号连接。
            dp[l][r][0] = range_sum(l, r);

            for (int t = 1; t < len; t++) {
                long long best = -1;

                // 最后一次运算可能是加号，也可能是乘号。
                // 枚举最后运算左右两边的区间和乘号数量。
                for (int mid = l; mid < r; mid++) {
                    int left_len = mid - l + 1;
                    int right_len = r - mid;

                    // 最后一次运算是加号：左右乘号数量之和为 t。
                    for (int x = 0; x <= t; x++) {
                        int y = t - x;
                        if (x >= left_len || y >= right_len) {
                            continue;
                        }
                        if (dp[l][mid][x] == -1 || dp[mid + 1][r][y] == -1) {
                            continue;
                        }
                        best = max(best, dp[l][mid][x] + dp[mid + 1][r][y]);
                    }

                    // 最后一次运算是乘号：当前这个乘号占 1 个。
                    for (int x = 0; x <= t - 1; x++) {
                        int y = t - 1 - x;
                        if (x >= left_len || y >= right_len) {
                            continue;
                        }
                        if (dp[l][mid][x] == -1 || dp[mid + 1][r][y] == -1) {
                            continue;
                        }
                        best = max(best, dp[l][mid][x] * dp[mid + 1][r][y]);
                    }
                }

                dp[l][r][t] = best;
            }
        }
    }

    cout << dp[1][n][k] << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(n5)O(n^5)
  • 空间复杂度：O(n3)O(n^3)

虽然看起来不低，但这里 n<=15n <= 15，完全足够。

总结

这题的关键是不要把“任意加括号”误化简成“段和相乘”。

正确做法是把最后一次运算作为区间 DP 的分界：最后是加号就做加法转移，最后是乘号就做乘法转移。 这样才能覆盖 (0 × 0) + 1 这类最后一步为加法的表达式。