P1018 [NOIP 2000 Senior] Maximum Product

NOIP2000 提高组 T2

The year 2000 was designated as the World Year of Mathematics by the International Mathematical Union, and it also marked the 90th birth anniversary of the renowned Chinese mathematician Hua Luogeng. In Jintan, Jiangsu, Hua Luogeng’s hometown, a special mathematics contest was held. Your good friend XZ participated, and the host posed the following problem: Given a numeric string of length $N$, insert $K$ multiplication signs to split it into $K + 1$ parts. Find a way to split it so that the product of these $K + 1$ parts is maximized. To help participants understand the problem, the host gave the following example: Given the numeric string $312$, when $N = 3, K = 1$, there are two ways to split it: 1. $3 \times 12 = 36$. 2. $31 \times 2 = 62$. In this case, the correct result is $31 \times 2 = 62$. Now, please help your friend XZ write a program to compute the correct answer.

The input consists of two lines: - The first line contains two natural numbers $N, K$. - The second line contains a numeric string of length $N$.

Output the maximum product (a natural number) corresponding to the given input.

Constraints - For $60\%$ of the testdata: $6 \le N \le 20$. - For all testdata: $6 \le N \le 40$, $1 \le K \le 6$. Translated by ChatGPT 5