算法
(区间DP) $O(n^3)$
本题本质上就是 石子合并
记 dp[i][j]
表示合并第 $i$ 只史莱姆到第 $j$ 只史莱姆所需的最小代价
转移方程:
$ dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k+1][j] + \sum\limits_{k=i}^j a_k) $
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
const ll LINF = 1001002003004005006ll;
const int MX = 405;
ll dp[MX][MX];
inline void chmin(ll& x, ll y) { if (x > y) x = y; }
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> s(n+1);
rep(i, n) s[i+1] = s[i] + a[i];
rep(i, n)rep(j, n) dp[i][j] = LINF;
drep(l, n)srep(r, l, n) {
if (l == r) dp[l][r] = 0;
else {
srep(k, l, r) {
chmin(dp[l][r], dp[l][k] + dp[k+1][r] + (s[r+1] - s[l]));
}
}
}
cout << dp[0][n-1] << '\n';
return 0;
}