[工学]石子划分实验动态规划算法设计c++

《[工学]石子划分实验动态规划算法设计c++》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、描述 给定n个石子，其重量分别为a1,a2,a3…,an，要求将其划分成m份，每一份的划分费用定义为这份石子中最大重量与最小重量的差的平方。总划分费用等于m份划分费用之和。输入 第一行两个正整数n和m，接下来有n行每行一个正整数，表示一个石子的重量ai。(1≤n,m,ai≤1,000)输出 将计算出的最小总划分费用输出样例输入4 24 7 10 1样例输出18描述 给定n个石子，其重量分别为a1,a2,a3…,an，要求将其划分成m份，每一份的划分费用定义为这份石子中最大重量与最小重量的差的平方。总划分费用等于m份划分费用之和。输入 第一

2、行两个正整数n和m，接下来有n行每行一个正整数，表示一个石子的重量ai。(1≤n,m,ai≤1,000)输出 将计算出的最小总划分费用输出样例输入4 24 7 10 1样例输出18代码：#include"stdafx.h"#include"stdio.h"#include#includeusingnamespacestd;inta[105],minvalue;intdp[105][105];intMin(intb[],intn,intm){intmin=b[n-1],j;for(j=n-1;j>=

3、m-1;j--)if(b[j]=m-1;j--){p=a[n]-a[j+1];b[j]=f(j,m-1)+p*p;}}dp[n][m]=Min(b,n,m);returndp[n][m];

4、};intmain(){inti,n,m;scanf("%d",&n);scanf("%d",&m);a[0]=0;for(i=1;i<=n;i++){scanf("%d",&a[i]);/*j=i;while(a[j]

5、[i]);minvalue=f(n,m);printf("%d",minvalue);return0;}运行结果：