Codeforces 229D Towers：動態規劃最少合併操作使塔高非遞減

題目簡介

有 n 座塔（n ≤ 5000），高度 h_i。每次操作可將一座塔移到相鄰塔頂（高度相加），被移動塔消失。求使塔高從左到右非遞減的最少操作數。

解題思路

動態規劃：dp[i][j] 表示前 i 座塔合併成若干段，最後一段以第 i 塔為結尾，且該段高度為 j（或用前綴和優化）。實際上可定義 dp[i] 為前 i 塔處理完後，最後一段的最小可能高度，轉移時枚舉最後一段的起點 k，段高 = sum[k..i]，需 ≥ 前一段高度。優化後 O(n^2)。

代碼框架

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, h[5005], sum[5005];
int dp[5005]; // dp[i] = 前 i 塔合法分段時，最後一段的最小高度

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        sum[i] = sum[i-1] + h[i];
    }
    fill(dp, dp+n+1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= i; k++) {
            int seg = sum[i] - sum[k-1];
            if (seg >= dp[k-1])
                dp[i] = min(dp[i], seg);
        }
    }
    // 答案 = n - 最大分段數，需另行計算分段數
    // 此處略過完整代碼，核心思想為上述 DP
}

關鍵點

• 操作數 = n - 最終塔數 = n - 分段數。
• DP 求最大分段數，條件：每段高度非遞減。
• 時間 O(n^2)，n=5000 可行。