AcWing 282. 石子合并
原题链接
简单
作者:
AC_
,
2021-01-28 00:19:49
,
所有人可见
,
阅读 325
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310;
int a[N];
int f[N][N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
a[i] += a[i - 1];
}
for (int len = 2; len <= n; len ++) {
for (int i = 1; i + len - 1 <= n; i ++) {
int l = i, r = i + len - 1;
f[l][r] = 1e9;
for (int k = l; k < r; k ++) {
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
}
}
}
cout << f[1][n];
return 0;
}