乘法问题

成绩 0 开启时间 2013年01月15日 星期二 16:00
折扣 0.8 折扣时间 2013年01月15日 星期二 16:00
允许迟交 是 关闭时间 2013年01月15日 星期二 16:00
输入文件 chf.in 输出文件 chf.out

问题描述
设有一个长度为 N 的数字字符串，分成 K+1 个部分，使得 K+1 个部 分的乘积最大。 例如 N=6 ，且数字字符串为 ‘ 310143 ' ， K=3. 此时可能有的情况有以 下各种：

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=3636
31 ＊ 0 ＊ 1 ＊ 43=0
31 ＊ 01 ＊ 4 ＊ 3=372
310 ＊ 1 ＊ 4 ＊ 3=3720

问题：当 N ，数字串， K 给出之后，找出一种分法使其乘积最大。

【输入格式】

    输入由两行组成，第一行有两个整数，n（1≤n≤30）、k（1≤n≤30）；n表示数字串长度、k表示乘号个数。第二行是数字串。

【输出格式】

    输出为一个整数，为乘积最大值。

【输入样例】

输入文件名：chf.in

9 4
321044105

输出文件名：chf.out

5166000