石子合并
问题描述：有多堆石子，排成一排，现将这堆石子合并成有堆，合并的规则是只能是相邻的两堆进行合并，合并所消耗的体力为两堆石子的重量。最后把所以消耗的体力加起来就是合并成一堆所需要的体力，而我们需要求体力的最小值。 问题解决：[i][j]表示从第i堆到第j堆的合并的集合，f[i][j]表示第i堆到第j堆合并的体力最小值。 这个集合怎么枚举表示呢？当然是把区间进行分割：下面列举分割 i,[i 1，j] [i,i 1],[i 2,j] '''''' [i,i k],[i k 1,j] k>=0&&k<j-i 怎么求f[i][j]呢？就是上面的最小体力值。 下面是求f[i][j]=min(f[i][i k] f[i k 1][j] s[j]-s[i-1]),s集合表示石子从开始到某一位置的重量和。 注意遍历，初始化
代码语言：javascript复制cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> v(n 1),s(n 1);
for(int i=1;i<=n;i )
{
cin>>v[i];
s[i]=s[i-1] v[i];
}
vector<vector<int>> f(n 1,vector<int>(n 1));
for(int len=2;len<=n;len )//长度为1的都是0，不需要从1开始遍历
{
for(int left=1;left len-1<=n;left )//从1开始生成长度为len的区间；并且不断更新区间——滑动区间。
{
int right=left len-1;
f[left][right]=2e10;//设成最大值，表示不能合并
for(int k=0;k<right-left;k )
f[left][right]=min(f[left][right],f[left][left k] f[left k 1][right] s[right]-s[left-1]);
}
}
cout<<f[1][n]<<endl;
return 0;
}
