【区间DP】算式

题意概括

给出 $n$ 个相对位置固定的非负整数，要求在这些数字之间填入 $k$ 个乘号和 $(n-k-1)$ 个加号。你可以通过任意添加括号来改变运算顺序，目标是找到一种运算安排，使得最终计算出的表达式结果最大。 数据保证 $2 \le n \le 15$，$0 \le k < n$，给定数字都在 $0$ 到 $9$ 之间，最终答案小于 $2^{31}$。

• 样例输入：5 个数字 1 2 3 4 5，共有 2 个乘号。
• 样例解释：将计算顺序组织为 $(1+2+3) \times 4 \times 5$，前三个较小的数字通过加法得到 $6$，再与后面的数字连乘，得到 $6 \times 4 \times 5 = 120$，这是能组合出的最大结果。

样例分析

对于给出的 $5$ 个数字，我们需要插入 $4$ 个运算符，其中规定包含 $2$ 个乘号，剩余 $2$ 个自然是加号。如果要让整体结果最大，一种直观的策略是让加法服务于乘法。也就是说，把加号放在数值较小的数字之间，先让它们通过加法累积出一个相对可观的基数，然后再用乘号将大块的值相乘。 将 1、2、3 分在一个括号内进行加法，得到 $6$。此时还剩下数字 4 和 5，以及分配好的 $2$ 个乘号。由于符号数量刚好，余下的部分只能是连乘，最终算式变为 $6 \times 4 \times 5$，计算结果为 $120$。这个顺序比优先乘小数字带来的增益大得多。

题目分析

任意添加括号来安排运算优先级，实质上是构建一棵表达式树。在这棵树中，每个节点代表一次加法或乘法运算，而它管辖的左右子树对应着原序列中连续的两段数字区间。既然每一段连续区间最终都会合并成一个值，我们就可以把大问题拆解成若干个相邻小区间的合并问题。

题目中的数字都是非负数，且运算符仅有加和乘。在这种情况下，无论外层执行加法还是乘法，最终结果都会随着内部子区间计算结果的增大而单调递增。因此，要求整个式子的最大值，只需求出它左右两部分子式的最大值即可。局部最优能够推导出全局最优，这满足动态规划的最优子结构。

定义状态 dp[l][r][p] 表示在区间 $[l, r]$ 内，准确使用 p 个乘号所能获得的最大结果。 当区间长度大于 $1$ 时，枚举一个分割点 $m$ 将当前区间分为 $[l, m]$ 和 $[m+1, r]$。假设左半部分分配了 c 个乘号，那么两部分合并的运算方式有两种可能： 若两段区间由加号连接，那么右半部分需要使用 p - c 个乘号，此时结果为左右部分最大值之和。 若两段区间由乘号连接，那么连接本身消耗了一个乘号，右半部分就只能使用 p - 1 - c 个乘号，此时结果为左右部分最大值的乘积。

在具体实现中，按照区间长度从小到大进行递推。对于长度为 $1$ 的单个数字，不需要任何运算符，它的最大值就是原数字本身。将所有状态初始化为 $-1$ 来标记无效状态，遇到无效状态直接跳过即可。最后 dp[1][n][k] 即是题解。

参考实现

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

ll dp[20][20][20];
ll a[20];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            for (int p = 0; p < 20; p++) {
                dp[i][j][p] = -1;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        dp[i][i][0] = a[i];
    }
    
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            for (int m = l; m < r; m++) {
                for (int p = 0; p <= k && p <= r - l; p++) {
                    for (int c = 0; c <= p; c++) {
                        if (dp[l][m][c] != -1 && dp[m + 1][r][p - c] != -1) {
                            dp[l][r][p] = max(dp[l][r][p], dp[l][m][c] + dp[m + 1][r][p - c]);
                        }
                    }
                    if (p > 0) {
                        for (int c = 0; c <= p - 1; c++) {
                            if (dp[l][m][c] != -1 && dp[m + 1][r][p - 1 - c] != -1) {
                                dp[l][r][p] = max(dp[l][r][p], dp[l][m][c] * dp[m + 1][r][p - 1 - c]);
                            }
                        }
                    }
                }
            }
        }
    }
    
    cout << dp[1][n][k] << "\n";
    
    return 0;
}

复杂度分析

时间复杂度：状态定义包含区间左端点、右端点和乘号数量三个维度，枚举状态需 $O(n^3)$。对于每个状态，需要枚举分割点和左区间分配的乘号数，这部分消耗 $O(n^2)$。综合起来时间复杂度为 $O(n^5)$。在 $n \le 15$ 的数据范围内，计算次数极少，运行非常高效。 空间复杂度：构建了一个大小固定的三维数组存储中间状态，空间开销为 $O(n^3)$。

https://www.luogu.com.cn/problem/P1388