经典超时代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2500;
// 纯暴力一个个合并
const int INF = 100'000 * ((1 + MAXN - 1) * (MAXN - 1) / 2 + 1);
int n;
int a[MAXN * 2 + 5];
int sum[MAXN * 2 + 5];
int f[MAXN * 2 + 5][MAXN * 2 + 5];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    int nn = n + n;
    for (int i = 1; i <= nn; i++)
        sum[i] = sum[i - 1] + a[i];
    int ans = INF;
    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= nn; l++)
        {
            int r = l + len - 1;
            if (len == 1)
                f[l][r] = 0;
            else
            {
                f[l][r] = INF;
                for (int mid = l; mid <= r - 1; mid++)
                {
                    f[l][r] = min(f[l][r],
                                  f[l][mid] + f[mid + 1][r] + sum[r] - sum[l - 1]);
                }
            }
            if (len == n)
                ans = min(ans, f[l][r]);
        }
    cout << ans;
    return 0;
}

优化

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2500;
// 纯暴力一个个合并
const int INF = 100'000 * ((1 + MAXN - 1) * (MAXN - 1) / 2 + 1);
int n;
int a[MAXN * 2 + 5];
int sum[MAXN * 2 + 5];
int f[MAXN * 2 + 5][MAXN * 2 + 5];
int bestMid[MAXN * 2 + 5][MAXN * 2 + 5];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    int nn = n + n;
    for (int i = 1; i <= nn; i++)
        sum[i] = sum[i - 1] + a[i];
    int ans = INF;
    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= nn; l++)
        {
            int r = l + len - 1;
            if (len == 1)
            {
                f[l][r] = 0;
                bestMid[l][r] = l;
            }
            else
            {
                f[l][r] = INF;
                for (int mid = bestMid[l][r - 1];
                     mid <= bestMid[l + 1][r]; mid++)
                {
                    int now = f[l][mid] + f[mid + 1][r] + sum[r] - sum[l - 1];
                    if (now < f[l][r])
                    {
                        f[l][r] = now;
                        bestMid[l][r] = mid;
                    }
                }
            }
            if (len == n)
                ans = min(ans, f[l][r]);
        }
    cout << ans;
    return 0;
}