《石子划分实验 动态规划 算法设计C++》由会员分享,可在线阅读,更多相关《石子划分实验 动态规划 算法设计C++(3页珍藏版)》请在金锄头文库上搜索。
1、描述 给定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 行每行
2、一个正整数,表示一个石子的重量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 d
3、pnm;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; 运行结果: