AcWing 282. 石子合并
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-21 14:10:31
,
所有人可见
,
阅读 274
#include <iostream>
using namespace std;
const int N = 310;
int s[N], f[N][N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &s[i]);
//首先来处理前缀
for (int i = 1; i <= n; i ++) s[i] += s[i - 1];
for (int len = 2; len <= n; len ++) {
//枚举起始位置
for (int i = 1; i + len - 1 <= n; i ++) {
//有了起始位置和长度之后, 此时可以来求出来区间的左右端点
int l = i, r = l + len - 1;
f[l][r] = 1e9; //此时一定要来进行初始化, 否则每一次计算结果都是0
//枚举分界点
for (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", f[1][n]);
return 0;
}