2150: 宝典2第十一章乘积最大

【题目描述】乘积最大(Happiness.cpp/c/pas) NOIP 2000

   古人云：“不谋万世者，不足谋一时；不谋全局者，不足谋一域。”张琪曼通过研究惊奇地发现，每个人一生的幸福指数可以用一个长度为n的十进制数字字符串来表示，并且可以通过全局统筹安排，将幸福指数分成k+1个部分应用在她感兴趣的不同领域，从而使得总体幸福值最强，所谓幸福值最强，是指使得k个部分的乘积为最大。例如n=6，k=3，且数字字符串为“310143”时，此时可能有的情况有下列各种：

   3×1×0×143=0

   3×1×01×43=129

   3×1×014×3=126

   3×10×1×43=1290

   3×10×14×3=1260

   3×101×4×3=3630

   31×0×1×43=0

   31×01×4×3=372

310×1×4×3=3720

从上面的结果可以看出，最大乘积为310×1×4×3=3720。

现在的问题时，当n，数字串和k给出之后，找出一种分法使其乘积为最大。

【输入格式】

第一行为两个整数，即n和k， 6≤n≤40，1≤k≤6

第二行为数字字符串。

【输出格式】

一个整数，即最大乘积。

【输入样例】

6 3

310143

【输出样例】

3720