1 //還是轉(zhuǎn)移方程搞懂了就沒問題 
 2 #include <iostream>
 3 using namespace std;
 4 #define MaxSize 205
 5 #define inf 0x7ffffff
 6 int f[MaxSize],dp[33][MaxSize],cost[MaxSize][MaxSize] ;
 7 //餐館位置、前j個餐館設(shè)立i個倉庫的最短距離、第i個餐館到第j個餐館的設(shè)立一個倉庫的最短距離
 8 inline int abs(int a){
 9     if(a<0)    a=-a;
10     return a;
11 }
12 inline int min(int a,int b){
13     return a<b?a:b;
14 }
15 int main(){
16     //freopen("in.txt","r",stdin);
17     int i,j,w,n,k,no=0;
18     while (scanf("%d %d",&n,&k),(n||k)){
19         for(i=1;i<=n;i++)
20             scanf("%d",&f[i]);
21         for(i=1;i<=n;i++)
22             for(j=i;j<=n;j++){
23                 int pos=(i+j)>>1,temp1=0;
24                 for(w=i;w<=j;w++)
25                     temp1+=abs(f[w]-f[pos]);
26                 if(pos&1){
27                     int temp2=0;            
28                     for(w=i;w<=j;w++)
29                         temp2+=abs(f[w]-f[pos+1]);
30                     cost[i][j]=min(temp1,temp2);
31                 }
32                 else
33                     cost[i][j]=temp1;
34             }
35         memset(dp,0,sizeof(dp));
36         for(i=1;i<=n;i++)
37             dp[1][i]=cost[1][i];
38         for(i=2;i<=k;i++)
39             for(j=i;j<=n;j++){
40                 dp[i][j]=inf;
41                 for(w=i-1;w<j;w++)
42                     dp[i][j]=min(dp[i][j],dp[i-1][w]+cost[w+1][j]);
43             }
44                 
45         printf("Chain %d\n",++no);
46         printf("Total distance sum = %d\n\n",dp[k][n]);
47     }
48     return 0;
49 }