2150: 宝典2第十一章乘积最大
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:31
Solved:31
Description
【题目描述】乘积最大(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