题目描述

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。

在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。

活动中，主持人给所有参加活动的选手出了这样一道题目：

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

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

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

1）3*12=36

2）31*2=62

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

现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。

输入格式
第一行共有2个自然数 N，K。

第二行是一个长度为 N 的数字串。

输出格式
输出所求得的最大乘积（一个自然数）。

数据范围
2≤N≤10,
1≤K≤6,
数据保证 K<N

样例

输入样例：
4 2
1231
输出样例：
62

算法1

(暴力枚举) $O(不知道)$

根据所剩乘号来枚举当前乘数，剩下k个乘号，那么必须要保留k个乘数，也就是说当前乘数只能枚举到n-k位。
例如1231中,当选择第一个乘数时，k=2,那么第一个乘数最多取到12停止(此时n-k=2，只能枚举到第2位)，12x3x1。
否则就变成，123x1x?，最后一位没有数字。

时间复杂度

不知道

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20;
char s[N];
int a[N];
int n,k_s;//输入的N和K
int res=0;
int sum[N];//记录当前总和
void dfs(int u,int k){
    if(u>n||k<0) return;//剪枝，可有可无，但是剪枝思想得有，ps：不能写成u>=n，因为最后一个乘数可能就是从最后一位开始枚举的。

    if(k==0){//当且仅当没有乘号要填入，那么就只剩下最后一位乘数，将最后一位乘数计算，并累乘得出结果

        int ss=0;//临时变量用来求和
        for(int i=u;i<=n-k;i++){//这里可以直接写成for(int i=u;i<=n;i++)，因为k=0，这里为了直观体现规律，所以保留k
            ss=ss*10+a[i];
        }
        sum[k]=ss;

        //cout<<"k="<<k<<":"<<sum[k]<<endl;//查看结果

        int maxn=1;
        for(int i=0;i<=k_s;i++)
            maxn*=sum[i];
        res=max(res,maxn);//累乘得出结果

        //cout<<"res:"<<res<<endl;//查看结果
        //cout<<endl;
        return ;
    }

    for(int i=u;i<=n-k;i++){//枚举开始位置，最多枚举到n-k位停止，因为至少要留下k位给另外几个乘数，
                            //例如1231中,当选择第一个乘数时，u=1,k=2,那么第一个乘数最多取到12停止，12*3*1
        int ss=0;
        for(int j=u;j<=i;j++){//对当前划分数字进行求和（即求出当前乘数），左边界为u，右边界为当前枚举的i
            ss=ss*10+a[j];
        }
        sum[k]=ss;//将临时变量赋给当前乘数

        //cout<<"k="<<k<<":"<<sum[k]<<endl;//查看结果
        dfs(i+1,k-1);
    }

}
int main()
{
    cin>>n>>k_s;
    for(int i=1;i<=n;i++){
         cin>>s[i];   
         a[i]=s[i]-'0';
    }
    dfs(1,k_s);
    cout<<res;

    return 0;
}