Loading... 给定一个长度为 `n` 的数字串，你需要在其中插入 `k` 个乘号，以使得得到的表达式的值最大。注意，在插入乘号后，每个数可以有前导零。 ### 输入格式 第一行包含两个整数 `n` 和 `k`，表示数字串的长度和要插入的乘号个数。 第二行包含一个长度为 `n` 的数字序列，表示给定的数字串。 ### 输出格式 输出一个整数，表示可以得到的最大结果。 ### 数据范围 * 1 ≤ k < n ≤ 10 ### 输入样例 ``` 4 2 1234 ``` ### 输出样例 ``` 144 ``` ### 题目分析 考虑到数据范围并不大（字符串长度不超过 10），我们可以考虑使用深度优先搜索（DFS）来解决这个问题。 为了更好地处理乘号的添加，我们可以采用马拉车算法的思想，将字符串的长度扩大一倍，即将原来的数字串如 `12345678` 变为以空格分隔的形式 `1 2 3 4 5 6 7 8`，这样便于在后续操作中插入乘号。 此外，我们可以进行剪枝优化，从而减少不必要的搜索：当 `k` 减去已经放置的乘号数量大于剩余数字的数量减 1 时，进一步的枚举已经没有意义，因为此时无法再插入足够数量的乘号。 ### 代码实现 ``` #include <iostream> #include <bitset> using namespace std; using ll = long long; const int N = 100; string bufs, s; int n, k; ll ans; bitset <N> bt; void dfs(int h) { if (bt.count() == k) { ll t = 1, p = 0; while(p < s.length()) { int temp = 0; while(p < s.length() && !bt[p]) if (!(p & 1)) temp = temp * 10 + (s[p++] - '0'); else ++p; t *= temp; ++p; } ans = max(ans, t); return ; } if (h >= s.length() || ((h & 1) && k - bt.count() > ((((n - 1) << 1) - h + 1) >> 1))) return ; dfs(h + 1); if (h & 1) { bt[h] = 1; dfs(h + 1); bt[h] = 0; } } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k >> bufs; for (auto& i : bufs) { s += i; s += ' '; } s.erase(s.end() - 1); dfs(0); cout << ans; return 0; } ``` 最后修改：2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏