J. *【动态规划：区间一维一边推】乘积最大

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

有一个长度为 $N$ 的数字串，使用 $K$ 个乘号将它分成 $K+1$ 个部分，使得这 $K+1$ 个部分的乘积能够为最大。

例如：一个 $N=3$ 的数字串 $312$ ，当 $K=1$ 时会有以下两种分法： $3×12=36$ 和 $31×2=62$ ，最大乘积为 $62$ 。

第一行两个整数 $N \ \ K \ (6 \le N \le 36，1 \le K \le 6)$ 。

第二行一个长度为 $N$ 的数字串。

一行一个整数，即最大乘积。

9 4
321044105