石子合并问题的 动态规划解法

王晓东版 //--石子合并问题 /*问题描述：在一个圆形操场的四周摆放着n堆石子，先要将石子有序的合并为一堆。规定每次只能选相邻的石子合并成一堆，并将新一堆的石子数 记录为该次合并的得分。试设计一个算法，记录n堆石子合并的最大和最小得分。 数据输入：由文件input.txt输入，第一行是正整数n，表示有n堆石子。第二行有n个正整数，分别表示每堆石子的个数， 结果输出：将计算结果输出到文件output.txt中，文件中第一行是最小得分，第二行是最大得分 解题思路：类似于矩阵连乘问题，可以用动态规划的方法来解决： （1）定义一个n*n的数

//--石子合并问题
/*问题描述：在一个圆形操场的四周摆放着n堆石子，先要将石子有序的合并为一堆。规定每次只能选相邻的石子合并成一堆，并将新一堆的石子数
            记录为该次合并的得分。试设计一个算法，记录n堆石子合并的最大和最小得分。
  数据输入：由文件input.txt输入，第一行是正整数n，表示有n堆石子。第二行有n个正整数，分别表示每堆石子的个数，
  结果输出：将计算结果输出到文件output.txt中，文件中第一行是最小得分，第二行是最大得分
  解题思路：类似于矩阵连乘问题，可以用动态规划的方法来解决：
            （1）定义一个n*n的数组A来存储合并石子的最小合并方式，由一开始的只有两堆石子要合并慢慢向上递归得到n堆石子合并的最小得分。
			（2）定义另一个于A同秩的矩阵B来存储各个合并中间的剖分
			*/
#include
using  namespace std;
int read（int A[][100]int B[][100]int C[]）
{    FILE *fp;
	//读取文件的函数，从文件中得到A的值并且初始化B
	if（（fp=fopen（“input.txt““r“））==NULL）
	{
		// 文件读取失败就直接退出程序
	    cout<<“文件读取失败！\n“;
		exit（0）;
	}
	else
	{
		//文件读取成功的话就开始得到n堆石子的个数放到A[i][i]（0		int n;
		fscanf（fp“%d\n“&n）;
		for（int i=1;i<=n;i++）
		{
			//初始化A和B
                for（int j=1;j<=n;j++

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         11  2010-11-29 12:36  石子合并问题\input.txt

     文件      74752  2010-11-30 00:57  石子合并问题\Debug\vc60.idb

     文件     110592  2010-11-30 00:56  石子合并问题\Debug\vc60.pdb

     文件    2002664  2010-11-30 00:47  石子合并问题\Debug\石子合并.pch

     文件     553025  2010-11-30 00:56  石子合并问题\Debug\石子合并.exe

     文件    1123328  2010-11-30 00:56  石子合并问题\Debug\石子合并.pdb

     文件     156452  2010-11-30 00:56  石子合并问题\Debug\石子合并.obj

     文件     792004  2010-11-30 00:56  石子合并问题\Debug\石子合并.ilk

     文件      41984  2010-11-30 00:57  石子合并问题\石子合并.ncb

     文件        758  2010-11-30 00:56  石子合并问题\石子合并.plg

     文件         10  2010-11-30 00:57  石子合并问题\output.txt

     文件       3427  2010-11-30 00:08  石子合并问题\石子合并.dsp

     文件        524  2010-11-30 00:47  石子合并问题\石子合并.dsw

     文件       3977  2010-11-30 00:56  石子合并问题\石子合并.cpp

     文件      48640  2010-11-30 00:57  石子合并问题\石子合并.opt

     目录          0  2010-11-29 12:40  石子合并问题\Debug

     目录          0  2010-11-29 10:31  石子合并问题

----------- ---------  ---------- -----  ----

              4912148                    17