上海基础微网站开发,wordpress 加视频教程,学校建设外文网站情况,windows优化大师的功能Description 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆#xff0c;并将新的一堆石子数记为该次合并的得分。请设计一个程序#xff0c;计算出将N堆石子合并成一堆的最小得分。 Input 每组数据第1行为一个…Description 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆并将新的一堆石子数记为该次合并的得分。请设计一个程序计算出将N堆石子合并成一堆的最小得分。 Input 每组数据第1行为一个正整数N(2N100)以下N行每行一个正整数小于10000分别表示第i堆石子的个数(1iN)。 Output 对于每组数据输出一个正整数即最小得分 Sample Input 7 13 7 8 16 21 4 18 Sample Output
239 解题过程
这道题老师讲过所以很快就Ok了其实主要是看书首先在书上找出求出动态转移方程我们可以用f[i][j]表示从i到j堆石头的最优解。
然后用s[i][j]表示从i-j石子堆的和。优化一下可以用s[i]表示前i堆的和让后s[j]-s[i-1]就可以做到s[i][j]的效果。
在枚举一个k表示从i-j的第k个开始分就可以求出来了。
然后动态转移方程f[i][j]min(f[i][j],f[i][k]f[k1][j]s[j]-s[i-1]) 代码
#includecstdio #includeiostream #includecstring using namespace std; int n,x,s[101],f[101][101]; int main() { scanf(%d,n); for (int i1;in;i) { scanf(%d,x); s[i]s[i-1]x;//s[i]表示前i堆的总和 } memset(f,127/3,sizeof(f));//给f赋值一个很大的数 for (int i1;in;i) f[i][i]0;//预处理 for (int in-1;i1;i--)//从n-1开始枚举头 for (int ji1;jn;j)//这样枚举可以从少堆的开始枚举 for (int ki;kj-1;k)//枚举分裂点 f[i][j]min(f[i][j],f[i][k]f[k1][j]s[j]-s[i-1]); //动态转移方程 printf(%d\n,f[1][n]);//输出从1-n堆最优解 }
