AcWing 282. 石子合并
原题链接
简单
作者:
szywdwd
,
2021-08-30 16:32:30
,
所有人可见
,
阅读 165
前缀和区间dp
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n;
int s[N]; // 前缀和数组
int dp[N][N];// dp[i][j]:区间[i, j]的合并最小代价
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i) cin >> s[i], s[i] += s[i - 1];
for(int len = 2; len <= n; ++len)
for(int i = 1; len + i - 1 <= n; ++i) {
int j = len + i - 1;
dp[i][j] = 1e9;
for(int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
}
cout << dp[1][n] << endl;
return 0;
}