题目理解

我们有 $n$ 座山，第 $i$ 座山的高度为 $a_i$。我们希望在尽可能少的挖掘工作量下，让尽可能多的山成为"山峰"（即比相邻的山严格高）。

对于每个 $k$（$1 \le k \le \lceil \frac{n}{2} \rceil$），我们需要找到建造 $k$ 座房子的最小挖掘时间。

问题分析

这是一个动态规划问题。关键观察是：

• 山峰不能相邻（因为一个山峰需要比两边都高）
• 当我们决定在某位置建房子时，可能需要降低相邻山的高度

动态规划状态设计

设 $f[i][j]$ 表示考虑前 $i$ 座山，第 $i$ 座山建了房子，总共建了 $j$ 座房子的最小代价。

设 $g[j]$ 表示考虑前 $i-2$ 座山，总共建了 $j$ 座房子的最小代价（用于辅助计算）。

状态转移

对于每个位置 $i$ 和房子数量 $j$：

1. 如果第 $i$ 座山建房子：

   • 需要确保 $a_i > a_{i-1}$ 和 $a_i > a_{i+1}$
   • 代价包括：
     • 降低 $a_{i-1}$ 的代价：$\max(0, a_{i-1} - a_i + 1)$
     • 降低 $a_{i+1}$ 的代价：$\max(0, a_{i+1} - a_i + 1)$
   • 有两种情况：
     • 从 $g[j-1]$ 转移（即前 $i-2$ 座山的最优解）
     • 从 $f[i-2][j-1]$ 转移，但要考虑 $a_{i-2}$ 对 $a_{i-1}$ 的影响

2. 更新 $g$ 数组：

   • $g[j] = \min(g[j], f[i-2][j])$

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, a[N], f[N][N / 2], g[N];

int main() {
    cin >> n;
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    g[0] = f[0][0] = 0;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= (i + 1) / 2; j++) {
            // 情况1：从g[j-1]转移
            f[i][j] = g[j - 1] + max(0, a[i - 1] - a[i] + 1) + max(0, a[i + 1] - a[i] + 1);

            // 情况2：从f[i-2][j-1]转移（需要i>2）
            if (i > 2)
                f[i][j] = min(f[i][j], 
                    f[i - 2][j - 1] + 
                    max(0, min(a[i - 2] - 1, a[i - 1]) - a[i] + 1) + 
                    max(0, a[i + 1] - a[i] + 1));
        }

        // 更新g数组
        if (i > 1)
            for (int j = 0; j <= (i + 1) / 2; j++)
                g[j] = min(g[j], f[i - 2][j]);
    }

    // 输出答案
    for (int i = 1; i <= (n + 1) / 2; i++)
        cout << min(f[n][i], min(f[n - 1][i], g[i])) << " \n"[i == (n + 1) / 2];

    return 0;
}

关键点解释

1. 边界处理：

   • 对于 $i=1$，只需要考虑右边邻居
   • 对于 $i=n$，只需要考虑左边邻居
   • 代码中的 max(0, ...) 确保只计算需要降低的高度

2. $g$ 数组的作用：

   • 记录前 $i-2$ 座山的最优解
   • 避免相邻山峰冲突

3. 最终答案：

   • 可能结束于第 $n$ 座山、第 $n-1$ 座山，或者更早
   • 取三者最小值确保找到全局最优

时间复杂度

• 状态数：$O(n^2)$
• 总时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$（可优化到 $O(n)$）

算法标签

• 动态规划
• 序列处理
• 最优化

这个解法通过巧妙的动态规划状态设计，高效地解决了山峰建造的最优化问题。