乘积最大

题目

有一个长度为 N 的数字串，要求使用 K 个乘号将它分成 K+1 个部分，找出一种分法，使得这 K+1个部分的乘积最大。

例如一个数字串：312， 当 N=3，K=1时会有以下两种分法：

1）3*12=36

2）31*2=62

这时，符合题目要求的结果是：31*2=62。

    输入格式：
    第一行共有2个自然数 N，K。第二行是一个长度为 N的数字串。输出格式输出所求得的最大乘积（一个自然数）。
        
    数据范围：
    2≤N≤10,
    1≤K≤6,
    数据保证 K<N
    
    输入样例：
    4 2
    1231
        
    输出样例：
    62

DFS

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 11;
    
    int n, k;
    char s[11];
    
    // 计算s从l--r的数字大小
    int sum(int l, int r)
    {
        int res = 0;
        for(int i = l; i <= r; i++)
            res = 10*res + (int)(s[i] - ‘0‘); 
        return res;
    }
    
    int dfs(int l, int r, int k)
    {
        if(k == 0) return sum(l, r);
        else if(r-l>=k)
        {
            int res = -1;
            for(int i = l; i < r; i++) //从i处分割，用掉一个乘号将l--r分为两部分。这里i<r和i<=r 都可AC
            {
                int left = sum(l, i);
                int right = dfs(i + 1, r, k-1);
                res = max(res, left * right);
            }
            return res;
        }
        return 0;
    }
    
    int main()
    {
        cin >> n >> k >> s+1;
        cout << dfs(1, n, k);
        return 0;
    }

乘积最大

原文：https://www.cnblogs.com/Winkelzyx/p/14589029.html