动态规划--石子合并的拓展问题

假期 2020.01.17

题目描述

一个圆形操场周围摆放着n堆石子，现要将石子有序的合并成一堆，规定每次只能移动相邻的两堆石子合并，合并花费为新合成的一堆石子的数量，求将这N堆石子合并成一堆的总花费（最小或最大）。

与此相似问题求解，请点击了解详情动态规划–石子合并

---

思路解答

这个问题其实是挺好理解的，但是如何转化是一个问题。一个圆形的摆放方式很明显是每一堆都是左右有相邻的堆的存在，那么为了将圆形的摆放方式转化为我们熟悉的直线型的摆放方式，我们可以将圆形的序列，如{A1,A2,A3,…,An}的圆形序列，改变成{A1,A2,A3,…,An,A1,A2,A3,…,A(n-1)},因为这样子可以保证每堆都是有左右相邻项的存在了。简单说来其实就是一种枚举吧，把每一种分割的可能都比较一次，赵卒后最优解即可。

---

代码解析

#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x0fffffff;//最大值
const int Scale = 300;//数据规模
int Min_weight[Scale][Scale], Max_weight[Scale][Scale];//最大花费，最小花费
int sum[Scale], Position[Scale];//，Scale前所有堆值，位置值
void Search_Stone(int Position[], int num)
{
	for (int i = 1; i <= num; i++) {//初始化
		Min_weight[i][i] = 0;
		Max_weight[i][i] = 0;
	}
	sum[0] = 0;//初始化
	for (int i = 1; i <= num; i++)//计算前堆i的累计石子数量
		sum[i] = sum[i - 1] + Position[i];
	for (int v = 2; v <= num; v++)//至少为两堆石子参加计算
	{
		for (int i = 1; i <= num - v + 1; i++)
		{
			int j = i + v - 1;//计算暂时终端点
			Min_weight[i][j] = INF;//初始化为最大值
			Max_weight[i][j] = -1;//初始化为最小值
			int temp = sum[j] - sum[i - 1];//记录i...j之间的石子数之和
			for (int k = i; k < j; k++) {
				Min_weight[i][j] = min(Min_weight[i][j], Min_weight[i][k] + Min_weight[k + 1][j] + temp);//选出最小值
				Max_weight[i][j] = max(Max_weight[i][j], Max_weight[i][k] + Max_weight[k + 1][j] + temp);//选出最大值
			}
		}
	}
}
void Circular_Stone(int Position[], int num,int &min,int &max)
{
	for (int i = 1; i <= num - 1; i++)//序列改变
		Position[num + i] = Position[i];
	num = num * 2 - 1;//扩展堆列
	Search_Stone(Position, num);//查找
	num = (num + 1) / 2;//复原
	min = Min_weight[1][num];
	max = Max_weight[1][num];
	for (int i = 2; i <= num; i++)
	{
		if (Min_weight[i][i + num - 1] < min)//查找最小值
			min = Min_weight[i][i + num - 1];
		if (Max_weight[i][i + num - 1] > max)//查找最大值
			max = Max_weight[i][i + num - 1];
	}
	return;
}
int main()
{
	int num;
	cout << "Please input the number of the stones: ";
	cin >> num;
	cout << "Please input the number of stones in each pile in turn: ";
	for (int i = 1; i <= num; i++)
		cin >> Position[i];
	int min = INF, max = -1;
	Circular_Stone(Position, num,min,max);
	cout << "最大花费是：" << max << endl;
	cout << "最小花费是: " << min << endl;
	return 0;
}

---

运行结果