问题描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n 堆石子合并成一堆的最小得分和最大得分。
【输入文件】
包含两行，第1 行是正整数n （1
第2行有n 个数，分别表示每堆石子的个数。
【输出文件】
输出两行。
第1 行中的数是最小得分；第2 行中的数是最大得分。
【输入样例】
4
4 4 5 9
【输出样例】
43
54
设计算法分析：
1）、此题表面上看是用贪心算法比较合适，实则不然，用贪心算法是每次都合
并得分最大的或最小的相邻两堆，但不一定保证余下的合并过程能导致最优解，聪明的读者马上会想到一种理想的假设：如果N －1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N －1次合并后的得分总和必然是最优的，这就是动态规划的思想。
采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。
这些石子堆子序列包括：｛第１堆、第２堆｝、｛第２堆、第３堆｝、……、｛第N 堆、第１堆｝；｛第１堆、第２堆、第３堆｝、｛第２堆、第３堆、第４堆｝、……、｛第N 堆、第１堆、第２堆｝；……｛第１堆、……、第N 堆｝｛第2堆、……、第N 堆、第１堆｝……｛第N 堆、第１堆、……、第N －１堆｝
为了便于运算，我们用〔i ，j 〕表示一个从第i 堆数起，顺时针数j 堆时的子序列｛第i 堆、第i ＋１堆、……、第（i ＋j ）堆｝（注意： 此时的i+j 可能已经超出N 的范围，为此 我们在读入每堆石子的数量时，把石子堆数扩展为2*N-1，有a[i]=a[i+N]，没有a[N+N]）
它的最佳合并方案包括两个信息：
② 该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和；
②形成最佳得分和的子序列１和子序列２。由于两个子序列是相邻的， 因此只需记住子序列１的堆数；
读者可以从以下详细的程序代码中体会到算法的思想：
// StonesMerger.h
#ifndef STONESMERGER_H
#define STONESMERGER_H
class StonesMerger
{
public:
StonesMerger();
~StonesMerger();
void run(); // 运行 接口
private:
int number; // 石子的堆数
int totalMax; // 记录合并成一堆的最 大 得分
int X; // 记录合并成一堆的最 大 得分的 最优合并的起始堆
int totalMin; // 记录合并成一堆的最 小 得分
int Y; // 记录合并成一堆的最 小 得分的 最优合并的起始堆
int *a; // 存储 石子的 数量
int **MAX; // 记录子序列合并最 大 得分
int **Smax; // 记录子序列合并最 大 得分的 最佳断开位置
int **min; // 记录子序列合并最 小 得分
int **smin; // 记录子序列合并最 小 得分的 最佳断开位置
bool input(); // 输入 接口 读取 input.txt 文件
void mostValue(); // 以第 i 堆开始 合并后面的 j 堆 j=0、1、
2、...... 、n-1
void output(); // 输出 显示
void traceback(int **s,int n,int m); //
smin[n][m] 寻找轨迹
};
#endif
// StonesMerger.cpp
#include
#include
#include
#include
#include "StonesMerger.h"
ifstream inputFile("input.txt",ios::in);
ofstream outputFile("output.txt",ios::out);
对应于或 Smax[n][m]
#define N 100 // 根据实际问题规模 大小 设定 恰当的 初值
StonesMerger::StonesMerger()
{
number=0;
X=0;
Y=0;
totalMax=0;
totalMin=0;
a=new int [2*N];
MAX=new int *[2*N];
Smax=new int *[2*N];
min=new int *[2*N];
smin=new int *[2*N];
for (int i=0;i
{
min[i]=new int [2*N]; MAX[i]=new int [2*N]; Smax[i]=new int [2*N];
}
}
smin[i]=new int [2*N];
StonesMerger::~StonesMerger()
{
delete []a;
for (int i=0;i
{
}
delete []MAX;
delete []Smax;
delete []min;
delete []smin;
}
delete []MAX[i]; delete []Smax[i]; delete []min[i]; delete []smin[i];
void StonesMerger::run() // 运行 接口
{
if (input())
{
}
}
bool StonesMerger::input()
{
if (!inputFile)
{
}
if (!outputFile)
{
}
mostValue(); output(); cerr
inputFile>>number;
outputFile
outputFile
for (int i=1;i
{
}
outputFile
if (a!=NULL)
{
}
return false;
}
void StonesMerger::output()
{
outputFile
traceback(smin,Y,number);
inputFile>>a[i]; a[i+number]=a[i]; outputFileoutputFile
outputFile
traceback(Smax,X,number);
outputFile
}
void StonesMerger::mostValue() // 寻找 最优 断开位置 和 最大 / 最小子序列
{
for (int i=1;i
{
}
for (int r=2;r
{
for (int i=1;i
int j=i; for (int m=1;m
if (T2
smin[i][r]=k;
}
} if (T1>MAX[i][r]) { } } } MAX[i][r]=T1; // 确保 子序列 最优 记录 最优断开位置 Smax[i][r]=k;
totalMax=0;
for (i=1;i
{
if (MAX[i][number]>totalMax) // 寻找 最大得分 并记录 最大得分的 序列的起始位置
}
totalMin=totalMax;
http://asizahuodian.taobao.com
{ totalMax=MAX[i][number]; X=i; }
for (i=1;i
{
if (min[i][number]
{
totalMin=min[i][number];
Y=i;
}
}
}
void StonesMerger::traceback(int **s,int i,int r) // 寻找轨迹
{
if (r==1)
{
outputFilenumber ? i%number : i);
}
else if(r==2)
{
outputFilenumber ? i%number
i)number ? (i+1)%number : (i+1))
}
http://asizahuodian.taobao.com
:
else
{
}
}
// main,cpp
#include "StonesMerger.h"
int main()
{
StonesMerger sm;
sm.run();
return 0;
}
http://asizahuodian.taobao.com
outputFile