资源描述
描述 给定n 个石子，其重量分别为a1, a2, a3, an，要求将其划分成m 份，每一份的划分费用定义为这份石子中最大重量与最小重量的差的平方。总划分费用等于m 份划分费用之和。输入 第一行两个正整数n 和m，接下来有n 行每行一个正整数，表示一个石子的重量ai。(1n, m, ai1,000)输出 将计算出的最小总划分费用输出样例输入4247101样例输出18描述 给定n 个石子，其重量分别为a1, a2, a3, an，要求将其划分成m 份，每一份的划分费用定义为这份石子中最大重量与最小重量的差的平方。总划分费用等于m 份划分费用之和。输入 第一行两个正整数n 和m，接下来有n 行每行一个正整数，表示一个石子的重量ai。(1n, m, ai1,000)输出 将计算出的最小总划分费用输出样例输入4247101样例输出18代码：#include stdafx.h#include stdio.h#include#includeusing namespace std; int a105,minvalue; int dp105105;int Min(int b,int n,int m) int min=bn-1,j;for(j=n-1;j=m-1;j-) if(bj=m-1;j-)p=an-aj+1; bj=f(j,m-1)+p*p; dpnm=Min(b,n,m);return dpnm;int main() int i,n,m; scanf(%d,&n); scanf(%d,&m);a0=0; for(i=1;i=n;i+) scanf(%d,&ai);/* j=i; while(ajaj-1) tap=aj; aj=aj-1; aj-1=tap; j-; */ / QuickSort(a,1,n); / MergeSort(a,n+1); sort(a+1,a+n+1); memset(dp,-1,sizeof(dp); / for(i=1;i=n;i+) / printf(%d,ai); minvalue=f(n,m); printf(%dn,minvalue);return 0; 运行结果：
展开阅读全文