AcWing 282. 石子合并
原题链接
简单
作者:
navystar
,
2023-05-24 21:47:14
,
所有人可见
,
阅读 141
状态转移模板
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 320;
int n;
int s[N], a[N], f[N][N];
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i], s[i] = s[i - 1] + a[i];
memset(f, 0x3f, sizeof f);
for (int len = 1; len <= n; len ++ )
for (int i = 1; i + len - 1 <= n; i ++ )
{
int j = len + i - 1;
if (len == 1)
{
f[i][j] = 0;
continue;
}
for (int k = i; k < j; k ++ )
if (f[i][j] > f[i][k] + f[k + 1][j] + s[j] - s[i - 1])
f[i][j] = f[i][k] + f[k + 1][j] + s[j] - s[i - 1];
}
cout << f[1][n] << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}