思路与算法

一次合并最终把原数组分成连续段，操作数为N减去段数。按段数k做DP：a[j]为前j座塔分成k-1段时最小末段和，不可行记INF。新末段(j,i]的和必须至少为a[j]，即前缀和S[j]+a[j]≤S[i]。把所有可行j按此阈值排序；扫描i时纳入阈值不超过S[i]的前驱，并维护最大的j，于是新末段和S[i]-S[j]最小。逐层直至整段不可分，取最大段数。

正确性说明

相同前缀和段数下，较小末段和不会妨碍任何后续分段，因此只保留最小值不损失最优解。所有合法前驱恰好满足阈值条件；正高度保证被纳入的j<i，选最大j使新末段最小。归纳每层DP精确，最大可行段数对应最少合并。

复杂度

前缀和与数组初始化O(N)。最多N层，每层排序O(NlogN)、扫描和清空O(N)，总O(N²logN)时间、O(N)额外空间；N≤3000且总高度≤9000000。

易错点

高度必须正；这保证阈值事件不会来自当前或未来前缀。段数相同需要比较末段和，不能只保留一个最大段数状态。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> s(n + 1);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        s[i] = s[i - 1] + x;
    }
    const int INF = 1000000000;
    vector<int> a(n + 1, INF), b(n + 1, INF);
    a[0] = 0;
    int best = 0;
    for (int k = 1; k <= n; k++) {
        vector<pair<int, int>> ev;
        for (int j = 0; j < n; j++)
            if (a[j] != INF)
                ev.push_back({s[j] + a[j], j});
        sort(ev.begin(), ev.end());
        fill(b.begin(), b.end(), INF);
        size_t at = 0;
        int mx = -1;
        for (int i = 1; i <= n; i++) {
            while (at < ev.size() && ev[at].first <= s[i]) {
                mx = max(mx, ev[at].second);
                at++;
            }
            if (mx >= 0 && mx < i)
                b[i] = s[i] - s[mx];
        }
        if (b[n] != INF)
            best = k;
        else
            break;
        a.swap(b);
    }
    cout << n - best << '\n';
}