Moe's CF Life

Appearance

D. Mathematical Problem - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 954 (Div. 3) 标签: brute force, dp, greedy, implementation, math, two pointers 难度: *1400

题目大意喵~ ​

主人你好呀！这道题是这样的：我们拿到一个长度为 n 的数字字符串 s，需要在它里面插入不多不少正好 n-2 个 + 号或者 * 号，把它变成一个算术表达式。我们的目标是，让这个表达式的计算结果最小最小，然后告诉人家这个最小值是多少，喵~

比如说，如果 s = "23311"，那 n=5，我们就得插入 5-2=3 个符号。我们可以把它变成 2+3+3+11，这里 11 是由两个 1 合并来的。

这里有个关键的小秘密哦！一个长度为 n 的字符串，数字之间有 n-1 个空隙可以放符号。现在我们要放 n-2 个符号，这意味着什么呢？这意味着，有且仅有一个空隙我们是不放符号的！不放符号，那两个相邻的数字就会贴在一起，组成一个两位数啦！其他的 n-2 个数字就都是一个个的单位数。

所以，题目就变成了：

  1. 从字符串 s 中，选择一对相邻的数字，把它们合并成一个两位数。
  2. 其他的数字都保持为单位数。这样我们就得到了一个由 n-1 个数（1个两位数，n-2个单位数）组成的序列。
  3. 在这个 n-1 个数的序列之间，插入 n-2 个 + 或 * 号，使得最终结果最小。

解题思路，喵~ ​

想要求最小结果，我们该怎么办呢？嘿嘿，让本喵来带你一步步分析！

第一步：找到所有可能的数字序列 ​

既然我们必须合并一对相邻的数字，而字符串长度 n 最大也只有 20，非常小，那我们完全可以把所有可能性都试一遍呀！这就是暴力枚举的思想，简单又有效，喵哈哈~

我们可以写一个循环，从 i = 0 到 n-2，每次循环都把第 i 位和第 i+1 位的数字（s[i] 和 s[i+1]）合并成一个两位数。这样，对于每一种合并方式，我们都会得到一个长度为 n-1 的数字列表。

举个例子，如果 s = "23311":

  • 合并 2 和 3，得到数字序列 {23, 3, 1, 1}
  • 合并 3 和 3，得到数字序列 {2, 33, 1, 1}
  • 合并 3 和 1，得到数字序列 {2, 3, 31, 1}
  • 合并 1 和 1，得到数字序列 {2, 3, 3, 11}

我们的任务就是对这每一种数字序列，都求出它能组成的最小表达式值，最后在所有这些最小值里再取一个最小的，就是最终答案啦！

第二步：对一个固定的数字序列求最小值 ​

好，现在问题简化了：给定一个数字序列 a_1, a_2, ..., a_m（这里 m = n-1），怎么插入 + 和 * 得到最小值呢？

这种处理一个序列，求最优解的问题，很自然地就会想到 动态规划 (Dynamic Programming) 了喵！

我们来定义一下 DP 状态： dp[i] 表示：使用数字序列的前 i+1 个数（也就是 a[0] 到 a[i]），所能构成的表达式的最小值。

接下来是最关键的 状态转移： 为了计算 dp[i]，我们考虑这前 i+1 个数构成的表达式中，最后一个加号放在哪里。因为乘法优先级高，整个表达式可以看成是“一堆乘积的和”，比如 T_1 + T_2 + ... + T_k。

当我们计算 dp[i] 时，最后一个项 T_k 可能是 a[i] 本身，也可能是 a[i-1] * a[i]，或者是 a[j] * ... * a[i]。 如果最后一个项是 a[j] * ... * a[i]，那么表达式就形如 (前 j-1 个数组成的最小表达式) + (a[j] * ... * a[i])。 前 j-1 个数组成的最小表达式 的值，不就是我们已经算出来的 dp[j-1] 吗？

所以，状态转移方程就出来啦： dp[i] = min(dp[j-1] + (a[j] * a[j+1] * ... * a[i]))，其中 j 从 i 遍历到 0。

当 j=0 时，表示整个 a[0...i] 序列全部相乘，没有加号，此时可以认为 dp[-1] 是 0。

特别注意的点喵：

  • 0 的妙用：零可是个好东西喵！任何数乘以零都得零！如果我们的数字序列里有 0，比如 {..., 5, 0, 8, ...}，那么把它们用乘法连起来 ...* 5 * 0 * 8 *... 这一整块就变成 0 了，这对我们求最小值非常有帮助！我们的 DP 方法可以自动发现这一点。
  • 1 的处理：1 在乘法里就像个小透明，x * 1 = x。但 x + 1 通常比 x * y (当y>1) 要小。所以，除非是为了连接到一个 0 上，我们通常更倾向于用加法来处理非 1 的数字。DP 同样能完美处理这种情况。

结合起来，我们的总算法就是：

  1. 外层循环遍历 n-1 种合并两位数的方式。
  2. 对于每一种方式，生成一个 n-1 个元素的数字列表 a。
  3. 使用 O(m^2) 的 DP（m=n-1）计算出这个列表 a 能构成的最小表达式值。
  4. 维护一个全局最小值 ans，每次 DP 算完都更新它。
  5. 最后输出 ans 就好啦！

代码实现，给你看哦~ ​

cpp
#include <iostream>
#include <vector>
#include <climits>
#include <cctype>
using namespace std;

// 使用 unsigned long long 是个好习惯，因为乘积可能会很大喵~
typedef unsigned long long ull;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        
        // 初始化一个超大的数，用来找最小值
        ull ans = ULLONG_MAX;
        
        // 喵~ 我们在这里枚举哪个位置 s[k] 和 s[k+1] 要合并成两位数
        for (int k = 0; k < n - 1; k++) {
            vector<ull> a; // 用来存放生成的数字序列
            
            // 把数字串 s 变成一个数字列表 a
            for (int i = 0; i < n; ) {
                if (i == k) {
                    // 这是我们要合并的两位数
                    ull num = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    a.push_back(num);
                    i += 2; // 跳过两位
                } else {
                    // 这是普通的单位数
                    a.push_back(s[i] - '0');
                    i++; // 跳过一位
                }
            }
            
            int m = a.size(); // 序列的长度总是 n-1
            vector<ull> dp(m, ULLONG_MAX); // dp[i] 表示处理到 a[i] 的最小结果
            
            // 这是DP的核心部分呐！
            for (int i = 0; i < m; i++) {
                ull product = 1;
                // 内层循环 j 从 i 倒着走，尝试所有可能的最后一个乘积项
                for (int j = i; j >= 0; j--) {
                    product *= a[j];
                    
                    if (j == 0) {
                        // 如果最后一个乘积项就是整个序列 a[0...i]
                        dp[i] = min(dp[i], product);
                    } else {
                        // 尝试在 j-1 和 j 之间放一个 '+'
                        // 表达式值为 (a[0...j-1]的最小值) + (a[j...i]的乘积)
                        ull candidate = dp[j - 1] + product;
                        if (candidate < dp[i]) {
                            dp[i] = candidate;
                        }
                    }
                }
            }
            
            // 每次算完一种两位数组合，都更新一下全局最小答案~
            if (dp[m - 1] < ans) {
                ans = dp[m - 1];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n³) 的说。
    • 最外层的循环，枚举合并位置 k，有 n-1 次，也就是 O(n)。
    • 对于每一种合并方式，我们都进行一次动态规划。
    • DP部分有两层循环，i 从 0 到 m-1，j 从 i 到 0（其中 m=n-1）。这部分的复杂度是 O(m^2)，也就是 O(n^2)。
    • 所以总的时间复杂度就是 O(n) * O(n^2) = O(n^3)。因为 n 最大才 20，20^3 = 8000，所以这个复杂度是完全可以接受的！
  • 空间复杂度: O(n) 的说。
    • 我们需要一个 vector<ull> a 来存储数字序列，它的长度是 n-1，所以是 O(n)。
    • DP数组 dp 的长度也是 n-1，也是 O(n)。
    • 所以总的空间复杂度就是 O(n)。

知识点与总结 ​

这道题真是个可爱又有趣的小综合题呢~ 它把好几个知识点巧妙地融合在了一起！

  1. 问题转化: 最重要的能力就是读懂题目背后的真正含义！“插入 n-2 个符号” 这个看似复杂的约束，其实被我们转化为了“选择一对相邻数字合并”这个更简单的操作，这是解题的关键一步喵。
  2. 暴力枚举 (Brute Force): 当问题规模很小的时候（n <= 20），不要害怕暴力！检查所有可能性是一种非常直接有效的策略。
  3. 动态规划 (DP): 这是解决序列最优值问题的经典武器。通过定义 dp[i] 为处理前 i 个元素的最优解，并通过思考最后一个操作来构建状态转移方程，是 DP 的核心思想。
  4. 注意数据范围: 表达式计算中，乘法可能让数字变得很大，所以使用 unsigned long long 是一个防止溢出的好习惯。

只要像这样把一个大问题，分解成一小步一小步可以解决的小问题，再复杂的题目也能被我们征服的喵！希望这篇题解能帮到你，加油哦，主人！💕

Released under the MIT License.

Copyright © 2024-present Moe