AcWing 282. 石子合并 C
原题链接
简单
作者:
LaChimere
,
2021-06-07 14:15:50
,
所有人可见
,
阅读 222
C
#include <stdio.h>
#include <limits.h>
#define MAXSIZE 310
#define min(a,b) ((a)<(b)?(a):(b))
int n, s[MAXSIZE], dp[MAXSIZE][MAXSIZE];
void init() {
scanf("%d", &n);
int weight;
for (int i = 1; i <= n; ++i) {
scanf("%d", &weight);
s[i] += s[i-1] + weight;
}
}
int main() {
init();
for (int len = 2; len <= n; ++len) {
for (int l = 1; l+len-1 <= n; ++l) {
int r = l + len - 1;
dp[l][r] = INT_MAX;
for (int k = l; k < r; ++k) {
dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
}
}
}
printf("%d\n", dp[1][n]);
return 0;
}