Solutions of Merging elements

Select solution language

bao987dz Created at 0 likes

Gọi $dp[i][j]$ là **chi phí tối thiểu** để gộp đoạn con từ $a[i]$ đến $a[j]$ thành $1$ phần tử. - Với đoạn con từ $i$ đến $j$, ta có thể chọn điểm $k (i <= k < j)$ để tách đoạn là 2 phần $a[i...k]$ và $a[k + 1...j]$ - Chi phí để gộp toàn bộ đoạn $i...j$ là: $$ dp[i][j] = \min_{i \leq k < j} \left( dp[i][k] + dp[k+1][j] + \text{sum}(i, j) \right) $$ Với $sum(i, j)$ là tổng các phần tử từ $a[i]$ đến $a[j]$ Độ phức tạp: $O(n^3)$ Code: ``` #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 503; const ll INF1 = 5e18; int n, a[MAXN]; ll pre[MAXN]; ll dp[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } for (int l = 2; l <= n; l++) { for (int i = 1; i + l - 1 <= n; i++) { int j = i + l - 1; dp[i][j] = INF1; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]); } } } cout << dp[1][n]; return 0; } ```