1602 问题 N: 蓝桥杯算法训练VIP-乘积最大

时间限制: 1s 内存限制: 128MB 提交: 757 解决: 388
题目描述
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

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

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

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

3*12=36
31*2=62

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

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入
程序的输入共有两行： 
第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 
第二行是一个长度为N的数字串。 
输出
输出所求得的最大乘积（一个自然数）。 
样例输入
4 2
1231
样例输出
62
提示
零基础同学可以先学习视频课程，包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程，提供视频讲解以及配套习题，还有老师答疑，点击这里了解课程详情

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
因为dotcpp的题集里没有专门练习搜索的题集，所以找了几个题目来练习搜索。
做题之前建议写出dfs bfs的模板，很多题套模板就能做出来了。
这些题目不是很难，不过一些dfs的题需要做些思考（可能因为我绕不来dfs）。
我只找了一些做过的搜索题，并不是很全，欢迎私信我补充题目。
以下为本次出现的题目：
2577 : 蓝桥杯2020年第十一届省赛真题-走方格
2352 : 信息学奥赛一本通T1440-数的划分
2276 : 蓝桥杯2018年第九届真题-全球变暖
2178 : 信息学奥赛一本通T1255-迷宫问题
2177 : 信息学奥赛一本通T1252-走迷宫
2171 : 信息学奥赛一本通T1329-细胞
2079 : 找寻小妖
2047 : x皇后问题
2046 : 输出全排列
1923 : 蓝桥杯算法提高VIP-学霸的迷宫
1825 : 蓝桥杯2015年第六届真题-穿越雷区
1796 : 蛇形填数
1672 : 迷宫问题
1602 : 蓝桥杯算法训练VIP-乘积最大
1551 : 蓝桥杯算法提高VIP-种树
1540 : 蓝桥杯算法提高VIP-棋盘多项式
1524 : 蓝桥杯算法提高VIP-扫雷
1518 : 蓝桥杯算法提高VIP-寻找三位数
1460 : 蓝桥杯基础练习VIP-2n皇后问题
1426 : 蓝桥杯历届试题-九宫重排
1266 : 马拦过河卒
1163 : 排队买票

                        

                    

                

                

                    

                        
比赛状况