废话不多说
//来自算法基础课
1.状态表示
f[i][j]表示i~j的某一区间
集合:所有的合并方法的集合
将第i堆石子和第j堆石子合并到一起的合并方式的最小消耗体力
属性:min
2.状态计算
集合划分:分类依据:最后一次合并的分界线k来分类
f[i][k] + f[k][j] + (s[j]-s[i-1])
我先把i~k合并到一起,
再把(k+1)~k合并到一起,
然后再把这两堆合并到一起
的最少消耗体力
但是我们思考的时候是虽然这么思考的,
实际处理的时候为了避免冗余我们并不是枚举l和r
而是枚举长度、左端点和中间分界线
然后用长度和左端点来推算出右端点
时间复杂度O(n^3)
初始化别忘了
1.取min要事先INF
2.f[i][i]相当于不合并,不耗体力
最终答案就是f[1][n]
因为我们要知道的区间是1~n这个区间嘛
CODE
#include<bits/stdc++.h>
#define read(n) scanf("%d",&n)
using namespace std;
const int N = 333;
const int INF = 2e9;
int n,f[N][N],s[N];
int main() {
read(n);
for(register int i=1; i<=n; i++) {
read(s[i]);
s[i] += s[i-1];//直接搞前缀和
}
for(register int i=1; i<=n; i++) //init
for(register int j=1; j<=n; j++)
if(i==j) f[i][j] = 0;
else f[i][j] = INF;
for(register int len=2; len<=n; len++)
for(register int l=1; l+len-1<=n; l++){
int r = l+len-1;
for(register int k=l; k<r; k++)
f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+(s[r]-s[l-1]));
}
printf("%d\n",f[1][n]);
return 0;
}