猫史档案馆

合并石子

有 n 堆石子堆放在路边,现要将石子有序地合并成一堆,规定每次只能移动相邻的两堆石子合并,合并花费为新合成的一堆石子的数量。求将这 N 堆石子合并成一堆的最小花费。

1. 设状态：f[i][j]表示从第i堆合并到第j堆，合并成一堆的最小得分

2. 初始状态：f[i][i]=0;

    最终状态：f[1][n];//从第1堆合并到第n堆的最小得分

3.状态转移方程：f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);

   在这里s[i]表示前i堆石头数量总和

 

这里符合动态规划性质：
总的来说就是设一个二维数组，可以理解为表示从起始位置到结束位置的最小权值，可以简单的理解为这里一个-邻接矩阵-。然后对这个邻接矩阵操作。每一个-权值-（-子问题-）都是由通过-最优化-当前的权值和枚举每个个中间点所形成的新权值而成的。新权值计算方法为起始位置到中间位置和中间位置到结束位置的最优权值和减去起始位置前缀和加上结束位置前缀和（就是再算这段的总数量）。

代码：

#include<iostream>
#include<cstring>
using namespace std;
int f[101][101];//f[i][j]表示从第i堆石头合并到第j堆石头最小得分（从问题出发，缩小规模） 
int s[101];//s[i]表示前i堆石头的数量总和 
int main()
{
	int n,x; 
	cin>>n;//有n堆石头
	for(int i=1;i<=n;i++)
	{
		cin>>x;//第i堆石头的个数
		s[i]=s[i-1]+x;//前i堆石头的数量总和 
	} 
	memset(f,127/3,sizeof(f));//将f[][]初始化为很大的一个值
	for(int i=1;i<=n;i++) f[i][i]=0;//初始状态
	for(int i=n-1;i>=1;i--)//从第i堆到第j堆，j>i,由后往前进行合并 
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=i;k<=j-1;k++)//k表示最后一次合并时是哪两堆进行合并，两堆：f[i][k],f[k+1][j](i<=k<=j-1) 
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);//s[j]-s[i-1]表示最后一次合并的得分 
			}
		}
	} 
	cout<<f[1][n]<<endl;
	return 0;
}