描述
输入格式
第一行两个正整数n和m,接下来一行有n个正整数,表示一个石子的重量ai。(1≤n, m, ai≤1000)
输出格式
计算输出最小总划分费用。 注意:若只有一个石子一份,那么,这份石子中最大重量与最小重量的差的平方为0。
输入样例
4 2 4 7 10 1
输出样例
18
///////////////////////////////////////////////////////////////////////
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 }
本文转自编程小翁博客园博客,原文链接:http://www.cnblogs.com/wengzilin/archive/2012/10/16/2726262.html,如需转载请自行联系原作者