【算法设计与分析】石子合并问题，对于给定n堆石子，计算合并成一堆的最小得分和最大得分。_python代码实现石子合并中最大得分和最小得分运行结果

一、问题描述

  在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的石子数记为该次合并的得分。试设计一种算法，计算出将n堆算法合并成一堆的最小得分和最大得分。
数据输入： 由文件input.txt提供输入数据，文件的第1行是正整数n(1≤n≤100),表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。
结果输出： 将计算结果输出到文件output.txt。文件第1行的数是最小得分，第2行中的是最大得分。

二、问题分析

  链式的石子合并问题是相邻两堆之间可以合并，那么环形的和链式的区别就在于环形的相当于是链式的头尾两堆也能合并，那么我们只要解决如何在链式的基础上更换每次头和尾的问题即可，即环形的切割点n堆，有n个切割点，每次以区间长度为n的链式的进行求解。我们创建长度为2*n的数组，存放两次石子序列即可。它的最优子结构和链式一样，把当前的链式区间划分的代价达到最优即可。
  在input.txt文本的第1行输入石子堆数，第2行输入每堆石子的个数，运行程序。

三、运行结果

  运行程序后，打开output.txt文本，文件第1行的数是最小得分，第2行中的是最大得分。

四、源代码

#include<iostream>
#include<fstream>
using namespace std;
int f[100][100];
int ff[100][100];
int v[100][100];
int a[100];
int n;
int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	in >> n; //n堆石子
	for (int i = 1; i <= n; i++) //每堆石子的个数
	{
		in >> a[i];
		a[i + n] = a[i];
	}

	for (int i = 1; i <= n * 2; i++)
	{
		for (int j = 1; j <= n * 2; j++)
		{
			if (i != j)
				f[i][j] = 10000;
		}
	}

	for (int i = 1; i <= n * 2; i++)
	{
		for (int j = i; j <= n * 2; j++)
		{
			for (int k = i; k <= j; k++)
			{
				v[i][j] += a[k];
			}
		}
	}

	for (int len = 1; len <= n; len++)//区间划分
		for (int l = 1, r = l + len; l < n * 2 && r < n * 2; l++, r = l + len)
		{
			for (int k = l; k < r; k++)  //选择区间分割点
			{
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + v[l][r]);
				ff[l][r] = max(ff[l][r], ff[l][k] + ff[k + 1][r] + v[l][r]);
			}
		}
	int ans1 = 10000, ans2 = 0;
	for (int i = 1; i <= n; i++) ans1 = min(ans1, f[i][i + n - 1]); //计算最小得分
	for (int i = 1; i <= n; i++) ans2 = max(ans2, ff[i][i + n - 1]);//计算最大得分
	out << ans1 << endl;
	out << ans2;
	in.close();
	out.close();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57