题目
设有 N 堆石子排成一排，其编号为 1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2堆，代价为 4，得到 4 5 2， 又合并 1、2堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
输出样例：
解题思路：
按区间从短到长依次枚举，求区间中石子合并的最小代价并记录在f数组中
例如
区间长度len=2时得到
f[1][2] = 4，f[2][3] = 8，f[3][4] = 7
在区间长度len=3时根据f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);就可以得到
f[1][3]=f[1][2]+f[3][3]+(s[3]-s[0])=13
ps：区间长度递增的原因是区间长度长的利用到了区间长度小的数值
程序代码
#include<bits/stdc++.h> const int N=1010; int f[N][N];//表示区间 int s[N]; //求前缀和 int a; using namespace std; int main() { cin>>a; for(int i=1;i<=a;i++)cin>>s[i]; for(int i=1;i<=a;i++)s[i]+=s[i-1];//求前缀和，使得下标之差就是区间的元素之和 for(int len=2;len<=a;len++)//len代表区间的长度，区间的长度递增 { for(int i=1;i+len-1<=a;i++)//例如，i=1，len=2时 i+len-1=2，1到2即表示区间长度为2 { int l=i,r=i+len-1; f[l][r]=0x3f3f3f3f; for(int k=l;k<r;k++)//k用来切割区间 { f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]); //区间从左到右依次分割求理想的最小值 } //s[r]-s[l-1]为最后一下合并区间内的石子需要的体力为区间内所有石子的和 } } cout<<f[1][a];//输出1到a区间的最小和，就是答案 }
| 
