思路与算法

先按x排序，离散化所有点的高度并加0。设f[h][l][r]为：在点l..r的水平范围内，假设高度不超过h的点已由外层矩形覆盖，覆盖剩余高点的最少额外矩形数。若左或右端点高度<=h，则跳过该端点。否则可在任意k处分成两个独立区间。还可放一个横跨xl..xr的外矩形；令H=floor(S/(xr-xl))（宽0则可取最大点高），若H覆盖两端点，就用1+f[H][l][r]补齐中间更高的点。因为H>=max(yl,yr)>h，依赖高度阈值严格升高，按h从高到低、区间长度从短到长求解。答案是f[0][0][n-1]。

正确性说明

两个落地矩形若水平范围交叉而非包含，重叠部分完全被较高矩形覆盖，可把较低矩形重叠侧截短，不丢失任何覆盖且面积不增。端点只移向已有端点，有限次截短后可得同数或更少矩形、水平范围两两分离或包含的层叠森林；外矩形若不低于内部矩形，则内部冗余可删除。于是最优解可按分离根区间划分，或在某区间用一个低外矩形覆盖低点、递归覆盖内部高点。外矩形的左右边可收缩到它实际负责的最左/最右点，故端点由点坐标决定；固定跨度时取面积允许最高H不会变差，正好对应1+f[H]转移。左右低点已被外层覆盖可免费跳过，区间分割和外层转移因此覆盖所有规范最优森林，且每个转移都给出真实可行矩形组合。DP取最小便是全局最优。矩形可以重叠；没有强加所有矩形互不相交的错误限制。

复杂度

设不同正高度数为H<=n。排序及高度压缩O(n log n)，预处理每个水平区间允许最高高度O(n² log n)，DP数组清零O(n³)。DP有O(Hn²)状态，每状态最多O(n)分割，因此时间O(n4)，空间O(n³)；在n<=100下使用unsigned char存最小矩形数（不超过100），数组约1.1MiB。多组输入上述成本对T组求和，已用T10、n100、100个不同高度的数据验证原1秒限制。

易错点

低矩形可以跨过被更高矩形单独覆盖的高点，普通不重叠连续分段DP不成立。面积上限限制的是宽乘高，不是点数。相同x的多点可以用零宽矩形覆盖，不能除以0；它们的最高点被覆盖时同位置低点也被覆盖。S和y均为正，点允许落在矩形边上，面积恰等于S仍合法。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
static unsigned char f[102][102][102];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, S;
        cin >> n >> S;
        vector<pair<int, int>> p(n);
        vector<int> ys(1, 0);
        for (auto &a : p) {
            cin >> a.first >> a.second;
            ys.push_back(a.second);
        }
        sort(p.begin(), p.end());
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        int H = ys.size();
        memset(f, 0, sizeof(f));
        vector<vector<int>> height(n, vector<int>(n));
        for (int l = 0; l < n; l++)
            for (int r = l; r < n; r++) {
                long long w = p[r].first - p[l].first;
                long long h = w ? S / w : ys.back();
                height[l][r] = upper_bound(ys.begin(), ys.end(), h) - ys.begin() - 1;
            }
        for (int h = H - 2; h >= 0; h--)
            for (int len = 1; len <= n; len++)
                for (int l = 0; l + len <= n; l++) {
                    int r = l + len - 1;
                    if (p[l].second <= ys[h]) {
                        f[h][l][r] = len == 1 ? 0 : f[h][l + 1][r];
                        continue;
                    }
                    if (p[r].second <= ys[h]) {
                        f[h][l][r] = len == 1 ? 0 : f[h][l][r - 1];
                        continue;
                    }
                    int ans = len, j = height[l][r];
                    if (j > h && p[l].second <= ys[j] && p[r].second <= ys[j])
                        ans = 1 + f[j][l][r];
                    if (ans > 1)
                        for (int k = l; k < r; k++)
                            ans = min(ans, (int)f[h][l][k] + f[h][k + 1][r]);
                    f[h][l][r] = ans;
                }
        cout << (int)f[0][0][n - 1] << '\n';
    }
}