题解

问题分析

我们需要选择最多 $k$ 个主对角线上的正方形，覆盖所有兴趣点，且覆盖的总格子数最小。

关键观察：

• 每个照片必须是主对角线上的正方形，即从 $(a,a)$ 到 $(b,b)$ 的正方形
• 一个兴趣点 $(r_i, c_i)$ 能被照片 $[a,b]$ 覆盖当且仅当：$$a \leq \min(r_i, c_i) \quad \text{且} \quad b \geq \max(r_i, c_i) $$

算法步骤

1. 预处理和简化

• 对每个兴趣点 $(r_i, c_i)$，计算：$$x_i = \min(r_i, c_i), \quad y_i = \max(r_i, c_i)$$
• 现在每个兴趣点对应一个区间 $[x_i, y_i]$
• 去除被包含的区间：如果 $[x_i, y_i] \subseteq [x_j, y_j]$，则去除 $[x_j, y_j]$
• 将区间按 $x_i$ 排序，此时 $y_i$ 也是递增的

2. 动态规划状态设计

设 $dp[i][j]$ 表示覆盖前 $i$ 个区间，使用 $j$ 张照片的最小总格子数。

状态转移：

$$dp[i][j] = \min_{0 \leq t < i} \{ dp[t][j-1] + (y_i - x_{t+1} + 1)^2 \} $$

其中 $(y_i - x_{t+1} + 1)^2$ 表示用一张照片覆盖区间 $t+1$ 到 $i$ 的代价。

3. 动态规划优化

优化1：决策单调性 对于固定的 $j$，设：

$$f_t(i) = dp[t][j-1] + (y_i - x_{t+1} + 1)^2$$

可以证明 $f_t(i)$ 具有决策单调性，即最优决策点 $t^*(i)$ 是单调不减的。

使用分治优化：

def solve(l, r, opt_l, opt_r):
    if l > r: return
    mid = (l + r) // 2
    best = INF, -1
    for t in range(opt_l, min(opt_r, mid) + 1):
        cost = dp[t][j-1] + (y_mid - x[t+1] + 1) ** 2
        if cost < best[0]:
            best = cost, t
    dp[mid][j] = best[0]
    solve(l, mid-1, opt_l, best[1])
    solve(mid+1, r, best[1], opt_r)

优化2：边界情况处理

• 当 $k \geq n$ 时，每个区间单独覆盖，答案为 $\sum (y_i - x_i + 1)^2$
• 当 $k = 1$ 时，答案为 $(y_n - x_1 + 1)^2$

4. 复杂度分析

• 预处理：$O(n \log n)$
• DP状态数：$O(nk)$
• 使用分治优化后，每个 $j$ 的复杂度：$O(n \log n)$
• 总复杂度：$O(nk \log n)$，对于 $n \leq 10^5$，$k \leq 100$ 可接受

样例验证

样例1：

n=5, m=7, k=2
点集: (0,3), (4,4), (4,6), (4,5), (4,6)

预处理后区间：

• (0,3) → [0,3]
• (4,4) → [4,4]
• (4,6) → [4,6]
• (4,5) → [4,5]
• (4,6) → [4,6]

去除重复和被包含后：

• [0,3], [4,4], [4,5], [4,6]

排序后： [0,3], [4,4], [4,5], [4,6]

最优解：用两张照片覆盖

• 照片1：[0,3]，代价 $4^2 = 16$
• 照片2：[4,6]，代价 $3^2 = 9$ 总代价：$16 + 9 = 25$ ✓

实现细节

1. 去重和简化：使用单调栈去除被包含区间
2. 初始化：$dp[0][0] = 0$，其他初始化为无穷大
3. 答案计算：$\min\limits_{1 \leq j \leq k} dp[n][j]$
4. 注意溢出：使用64位整数存储结果

总结

本题的核心在于：

1. 将几何问题转化为区间覆盖问题
2. 发现决策单调性并使用分治优化
3. 合理处理边界情况和状态初始化

通过巧妙的预处理和动态规划优化，可以在规定时间内求解大规模数据。