AcWing 282. 石子合并
原题链接
简单
作者:
harrytsz
,
2020-12-29 18:44:25
,
所有人可见
,
阅读 344
DFS 版本
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310, INF = 0x3f3f3f3f;
int f[N][N], sums[N], a[N];
int n;
int dfs(int l, int r) {
if(f[l][r] < INF) return f[l][r];
if(l >= r) return f[l][r] = 0;
for(int k = l; k < r; k++) {
f[l][r] = min(f[l][r], dfs(l, k) + dfs(k+1, r));
}
f[l][r] += sums[r] - sums[l-1];
return f[l][r];
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sums[i] = sums[i-1] + a[i];
}
memset(f, INF, sizeof f);
cout << dfs(1, n) << endl;
return 0;
}