网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
乘积最大
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 15:20 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 15:20 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 15:20 |
输入文件 | Happiness.in | 输出文件 | Happiness.out |
【题目描述】乘积最大(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