1 /********************************************
 2 程序总体思想
 3 
 4 1,先将石子重量从小到大排序(从大到小也可以).
 5 2,假设f(n,m)表示:n个石头分成m份的最小费用. 特别的,有f(1,1)=0; f(n,1)=(an - a1)^2
 6 那么,除去最后一份石头的若干个,前面m-1份必定也是最优的分法.
 7 若最后一堆1个石头, f(n,m) = f(n-1,m-1)+0^2
 8 若最后一堆2个石头, f(n,m) = f(n-2,m-1)+(an - an-1)^2
 9 若最后一堆3个石头, f(n,m) = f(n-3,m-1)+(an - an-2)^2
10 ......
11 最后一堆最多只能有n-m+1个石头,因为当最后一堆为n-m+1时,前面m-1堆已经是一个一份了.
12 因此, f(n,m) = Min{ f(n-1,m-1)+0^2,  f(n-2,m-1)+(an - an-1)^2,  ...}
13 
14   例如:
15   n=5, m=2
16   a[1..5] = 1 3 4 8 9
17   f(5,2)=Min{ f(4,1)+0; f(3,1)+1; f(2,1)+5^2 }=Min{49,10,29}=10
18 这5个石头分2堆的最优分法：（1 3 4）（8 9）
19 
20 ********************************************/
21 
22 
23 
24 #include "StdAfx.h"
25 #include <algorithm>
26 #include <iostream>
27 #include <stdio.h>
28 
29 using namespace std;
30 
31 #define MAX_NUM 10000000  
32 // d[i][j]表示从i到n分成j份的最小划分费用,i=0 或 j=0不用
33 
34 inline int Min(int a,int b)
35 {
36     if(a>b)
37         return b;
38     else
39         return a;
40 }
41 
42 int Divide(const int list[],const int &totalNum, const int &divCount,const int &list_length)
43 {
44     int i,j,k,t;
45     int d_size = list_length + 1;// i,j=0的时候不用
46     int **d = new int *[d_size];
47     for (i = 0; i < d_size; i++)
48     {
49         d[i] = new int[d_size];
50     }
51     
52     for(i=1;i<=totalNum;i++)
53     {
54         d[i][1]=(list[i]-list[1])*(list[i]-list[1]);
55         t=Min(i,divCount);
56         for(j=2;j<=t;j++)
57         {  
58             d[i][j]=MAX_NUM;
59             for(k=1;k<i;k++)
60             {
61                 d[i][j]=Min(d[i][j],d[k][j-1]+(list[i]-list[k+1])*(list[i]-list[k+1]));    //    重点
62             //    cout<<d[i][j]<<"\n";
63             }
64         }
65     }
66     
67     int minCost = d[totalNum][divCount];
68     //    释放二维数组内存
69     for (i = 0; i < d_size; i++)
70     {
71         delete[] d[i];
72     }
73     delete []d;
74     
75     return minCost;
76 }
77 
78 int main()
79 {
80     //    石头数、份数
81     int totalNum, divCount, weight, i, minDivCost = 0;
82     cin>>totalNum>>divCount;
83     //    list[0]不用
84     int *list = new int[totalNum+1];
85     for (i = 1; i <= totalNum; i++)
86     {
87         cin>>weight;
88         list[i] = weight;
89     }
90     sort(list+1, list + totalNum+1);
91     minDivCost = Divide(list, totalNum, divCount, totalNum);
92     cout<<minDivCost<<endl;
93 
94     delete []list;
95     return 0;
96 }