#63. 乘积最大

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: LinearCircle

题目描述

输入一个长度为 NNN 的数字串, 用 KKK 个乘号将它分为 (K+1) (K+1) (K+1) 个部分,使得得到的乘积最大

例如 N=3N = 3N=3 , K=1K = 1K=1 ,输入的数字串为 312

分法有两种

3∗12=363 * 12 = 36312=36

31∗2=62 31 * 2 = 62312=62

最大值为 626262

输入格式

输入共两行

第一行,正整数 NNNKKK

第二行,一个数字串

输出格式

KKK 个乘号将数字串划分为 K+1K+1K+1 个部分所得到的最大乘积

样例

样例输入1

3 1
312

样例输出1

62

样例输入2

7 3
3314245

样例输出2

278040

数据范围与提示

2≤N≤302 \le N \le 302N30

1≤K≤101 \le K \le 101K10

温馨提示:本题不需要额外写高精度,用 long long 即可.

(改编自2000年全国NOIP提高组试题)