题目分析：[JXOI2018] 守卫

1. 核心性质：最右侧必须有保镖

题目要求计算区间 $[l, r]$ 的最小保镖数。由于保镖只能向左看（即只能监视横坐标小于自己的亭子），那么对于区间最右端的亭子 $r$，必须由位于 $r$ 处的保镖来监视。因为区间 $[l, r]$ 内任何 $k < r$ 的位置都无法向右看到 $r$。

• 结论：在计算 $DP[l][r]$ 时，我们可以确定位置 $r$ 必定放置了一个保镖。

2. 视野与区间划分

当我们在 $r$ 处放置保镖后，他向左看会看到一系列“山峰”。假设从 $r$ 向左看，依次看到的亭子是 $p_1, p_2, \dots$（其中 $p_1$ 是离 $r$ 最近的可见点）。

• 这些可见点将区间 $[l, r]$ 切割成了若干个不可见的“山谷”。
• 例如，在 $p_1$ 和 $r$ 之间（不含 $p_1$ 和 $r$）的亭子是 $r$ 无法看到的，这些亭子必须由区间 $[p_1+1, r-1]$ 内部的保镖来负责。
• 同理，在 $p_2$ 和 $p_1$ 之间的亭子，必须由 $[p_2+1, p_1-1]$ 内部的保镖负责。

3. 动态规划状态定义

设 $dp[l][r]$ 表示：只考虑区间 $[l, r]$，且必须覆盖该区间所有亭子所需的最少保镖数。 根据性质 1，这个状态隐含了 $r$ 处一定有一个保镖。

算法逻辑与代码解析

状态转移方程

我们固定右端点 $r$，枚举左端点 $l$ 从 $r-1$ 到 $1$。 我们需要维护一个变量 pos，它表示在当前 $l$ 的右侧（即 $(l, r)$ 范围内），$r$ 能看到的离 $l$ 最近的一个点。

对于当前的 $l$，有两种情况：

1. $r$ 能看到 $l$：

   • 这意味着 $l$ 也是一个“山峰”。
   • 此时，$(l, pos)$ 之间形成了一个“山谷”，$r$ 看不到这里面的点。我们需要加上覆盖这个山谷的代价。
   • 山谷区间是 $[l+1, pos-1]$。但是，为了覆盖这个区间，我们可能需要在 $pos$ 处放保镖（看向左边覆盖山谷），也可能不需要（如果山谷内部自己能解决）。
   • 由于 $pos$ 已经被 $r$ 看到（即 $pos$ 本身已被覆盖），我们在解决子区间 $[l+1, pos]$ 时，可以选择“强制在 $pos$ 放保镖”或者“不在 $pos$ 放保镖”。
   • 根据贪心/DP思想，这部分的代价是 $\min(dp[l+1][pos], dp[l+1][pos-1])$。
   • 更新 sum（记录了从 $l$ 到 $r$ 之间所有已解决的山谷的总代价）。
   • 更新 pos = l。
   • 此时，$dp[l][r] = sum$（因为 $l$ 被 $r$ 直接覆盖，且右边的山谷都已计算在 sum 中）。

2. $r$ 看不到 $l$：

   • 这意味着 $l$ 处于当前 pos 和某更远点之间的山谷里。
   • $l$ 目前被“埋”在以 pos 为右端点的子问题中。
   • 我们不需要更新 sum，也不更新 pos。
   • 当前的代价是：右边已确定的代价 sum + 解决当前山谷延伸到 $l$ 的代价。
   • 即 $dp[l][r] = sum + \min(dp[l][pos], dp[l][pos-1])$。

斜率判断 (Slope Function)

代码中的 slope 函数用于判断 $r$ 是否能看到 $l$。 若 slope(pos, r) > slope(l, r)，说明 $l$ 相对 $pos$ 并没有被遮挡（在几何上，$l$ 在 $r-pos$ 连线的上方），因此 $r$ 能看到 $l$。

代码详细注释

#include <bits/stdc++.h>
using namespace std;

int h[5005];
int dp[5005][5005];

// 计算两点连线的斜率
double slope(int l, int r) {
    return (double)(h[r] - h[l]) * 1.0 / (double)(r - l);
}

int main() {
    // 优化 I/O
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, ans = 0;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        dp[i][i] = 1; // 边界：区间只有一个点，必须放1个保镖
    }

    // 区间 DP：枚举右端点 r
    for (int r = 2; r <= n; r++) {
        int pos = 0; // pos 记录 r 向左看时，最近的一个可见点
        int sum = 1; // sum 记录当前 r 视线下的总保镖数，初始为1是因为 r 本身有一个保镖

        // 枚举左端点 l，从 r-1 向左延伸
        for (int l = r - 1; l; l--) {
            // 判断可见性：
            // !pos: 初始情况，l 是 r 左边第一个点，必然可见
            // slope(...) > slope(...): 几何性质，如果旧斜率 > 新斜率，说明 l 没被 pos 挡住
            if (!pos || slope(pos, r) > slope(l, r)) {
                // 如果 r 能看到 l，说明 (l, pos) 之间是一个独立的山谷
                // 我们需要结算这个山谷的代价，加到 sum 中
                // min(dp[l+1][pos-1], dp[l+1][pos]) 表示是否利用 pos 处的保镖来向左覆盖山谷
                sum += min(dp[l + 1][pos - 1], dp[l + 1][pos]);
                
                // 更新 pos，因为 l 变成了新的最近可见点
                pos = l;
            }
            
            // 计算 dp[l][r]
            // 如果 l 可见，上方 if 执行了，dp[l][r] 就是 sum + min(..., l) 的逻辑，但因为 l 可见，
            // l 本身被 r 覆盖，不需要额外代价，且 sum 已经包含了右侧所有代价。
            // 这里代码写得非常精简：
            // 实际上如果 if 成立，dp[l][r] 应该等于 sum。
            // 但为了统一处理 "l 不可见" 的情况，代码用了统一公式：
            // sum + min(dp[l][pos], dp[l][pos-1])
            // 注意：当 if 成立时，pos 刚被更新为 l。
            // 所以 dp[l][pos] 变成了 dp[l][l] (是1)，dp[l][pos-1] 变成了 dp[l][l-1] (是0)。
            // min(1, 0) 是 0。所以 dp[l][r] = sum + 0 = sum。逻辑是自洽的。
            
            // 如果 if 不成立 (l 不可见)，pos 还是右边那个山峰。
            // l 属于 (..., pos) 这个山谷，我们需要付出覆盖 [l, pos] 的代价。
            dp[l][r] = sum + min(dp[l][pos], dp[l][pos - 1]);
        }
    }

    // 统计答案，题目要求所有 [l, r] 的答案异或和
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            ans ^= dp[i][j];

    cout << ans;
    return 0;
}

复杂度分析

• 时间复杂度：两层循环枚举 $l$ 和 $r$，内部操作为 $O(1)$，总复杂度 $O(n^2)$。对于 $n \le 5000$，运算量约为 $2.5 \times 10^7$，在 1000ms 时限内可以轻松通过。
• 空间复杂度：需要 $O(n^2)$ 的数组存储 DP 状态，约 $25 \text{MB}$，符合 512MB 的限制。