P2217 [HAOI2007] Splitting the Matrix

Partition an $a \times b$ numeric matrix as follows: cut the original matrix along a straight line into two matrices, then continue partitioning the resulting matrices in the same way (you may also choose to partition only one of them). After $(n - 1)$ cuts, the original matrix is partitioned into $n$ matrices. Each cut may only be made along the gaps between numbers (i.e., along the grid lines between cells). Each position in the original matrix has a score. The total score of a matrix is the sum of the scores at all positions it contains. Now, you need to partition the matrix into $n$ matrices according to the above rule, minimizing the mean square deviation of the total scores of the matrices. Given the matrix and $n$, write a program to compute the minimal value of the mean square deviation.

The first line contains 3 integers, the values of $a, b, n$ $(1 < a, b, n \le 10)$. From the second line to the $(a + 1)$-th line, each line contains $b$ non-negative integers less than $100$, representing the score at the corresponding position in the matrix. Adjacent numbers in each row are separated by a single space.

Output a single number: the minimal mean square deviation, rounded to two decimal places.

Translated by ChatGPT 5