#include <iostream>#include <cstdlib>#include <stdio.h>using namespace std;int data[220];int mindis[220][220];int result[220][40];int n, k;int searchResult(int n, int k){if(n <= k) return 0;if(k == 1)return mindis[1][n];if(result[n][k] != -1)return result[n][k];int min = 999999999;int i;for(i = k - 1; i < n; i++){int temp = searchResult(i, k - 1) + mindis[i + 1][n];if(temp < min)min = temp;}result[n][k] = min;return min;}int main(){int iCase=0;while(cin >> n >> k && n && k){int i, j;for(i = 1; i <= n; i++){cin >> data[i];for(j = 0; j <= n; j++)result[i][j] = -1;}int mid;for(i = 1; i <= n; i++){mindis[i][i] = 0;for(j = i + 1; j <= n; j++){int p;mindis[i][j] = 0;mid = (i + j) / 2;for(p = i; p <= j; p++)mindis[i][j] += abs(data[p] - data[mid]);}}cout<<"Chain " << ++iCase << endl;cout<<"Total distance sum = "<< searchResult(n , k ) << endl << endl; }return 0;}
