Estimation#3975
"
textitThere are too many numbers here!" your boss bellows. "
textitHow am I supposed to make sense of all of this? Pare it down! Estimate!"
You are disappointed. It took a lot of work to generate those numbers. But, you'll do what your boss asks.
You decide to estimate in the following way: You have an array of numbers. You will partition it into contiguous sections, which won't necessarily be of the same size. Then, you'll use a single number to estimate an entire section. In other words, for your array of size , you want to create another array of size , which has contiguous sections. If and are in the same section, then B_i=B_j. You want to minimize the error, expressed as the sum of the absolute values of the differences (\sum|A_i-B_i|).
There will be several test cases in the input. Each test case will begin with two integers on a line, (1 \le n \le 2000) and (1 \le k \le 25, k \le n), where is the size of the array, and is the number of contiguous sections to use in estimation. The array will be on the next lines, one integer per line. Each integer element of will be in the range from to , inclusive. The input will end with a line with two s.
For each test case, output a single integer on its own line, which is the minimum error you can achieve. Output no extra spaces, and do not separate answers with blank lines. All possible inputs yield answers which will fit in a signed -bit integer.
Παράδειγμα 1