给定一个长度为 n 的数字串,你需要在其中插入 k 个乘号,以使得得到的表达式的值最大。注意,在插入乘号后,每个数可以有前导零。

输入格式

第一行包含两个整数 nk,表示数字串的长度和要插入的乘号个数。

第二行包含一个长度为 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;
}
分类: DFS

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status