就是一个简单的区间DP
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sc(a) scanf("%lld", &a)
#define pr(a) printf("%lld", a)
#define N 305
ll n, a[N], f[N][N], s[N];
int main()
{
memset (f, 0x3f3f3f3f, sizeof f);
sc(n);
for (int i = 1; i <= n; ++i){
sc(a[i]);
s[i] = s[i - 1] + a[i];
f[i][i] = 0;
}
for (int len = 2; len <= n; ++len){
for (int l = 1; l <= n - len + 1; ++l){
ll r = l + len - 1;
for (int k = l; k < r; ++k){
f[l][r] = min(f[l][k] + f[k + 1][r], f[l][r]);
}
f[l][r] += s[r] - s[l - 1];
}
}
pr(f[1][n]);
}
求关注 点赞 评论 收藏