题解 ljz
2024-07-27 17:11:43
发布于：浙江
9阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
int a[305],dp[305][305],s[305];
int main() {
int n;
cin >> n;
for (int i = 1;i <= 300;i ++) {
for (int j = 1;j <= 300;j ++) {
dp[i][j] = 1e9+7;
}
}
for (int i = 1;i <= n;i ++) {
cin >> a[i];
s[i] = s[i-1] + a[i];
dp[i][i] = 0;
//顶点i到顶点i的合并权值为0
}
for (int i = 2;i <= n;i ++) {
// 设定当前合并的区间范围长度
for (int j = 1;j <= n - i + 1;j ++) {
// 枚举范围的起点设置为i
int k = j + i - 1;
// k为当前合并范围的终点
for (int l = j;l <= k - 1;l ++) {
// l为分割点 枚举所有可以分割的顶点
dp[j][k] = min(dp[j][k],dp[j][l]+dp[l+1][k]+s[k]-s[j - 1]);
}
}
}
cout <<dp[1][n];
}
有帮助，赞一个