CSES 2088：Knuth Division

CSES 2088：Knuth Division

題目大意：給一個陣列，一開始全部元素為一個區間，想要經過多次分裂使一個元素為一個區間，每次分裂的代價是待分裂區間元素之總和，求最小所需代價。

解法：無情四邊形優化 …。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int INF = 1e18;
 
void solve() {
    int n;
    cin >> n;
 
    int pre[n + 1] = {}, dp[n + 1][n + 1], best[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            dp[i][j] = INF;
        cin >> pre[i];
        dp[i][i] = 0;
        best[i][i] = i;
        pre[i] += pre[i - 1];
    }
 
    for (int len = 2; len <= n; len++) {
        for (int l = 1, r = len; r <= n; l++, r++) {
            for (int k = best[l][r - 1]; k <= best[l + 1][r] && k < r; k++) {
                if (dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1] < dp[l][r]) {
                    dp[l][r] = dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1];
                    best[l][r] = k;
                }
            }
        }
    }
 
    cout << dp[1][n] << '\n';
}
 
int32_t main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！