[USACO08MAR] Land Acquisition G

GitHub跳转原题关系图返回列表

先删除所有被支配矩形，把问题化成连续分段 DP，再用单调队列维护凸包优化转移。

OJ: luogu

题目 ID: P2900

难度:提高+/省选-

标签:动态规划斜率优化凸包优化贪心预处理

日期: 2026-06-21 07:31

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

每块土地有长和宽。

如果单买一块，花费是面积。 如果把若干块一起买，花费是：

这一组最大的长 * 这一组最大的宽

要求把所有土地分组，最小化总花费。

思路

先看朴素 DP：

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

const long long INF = (1LL << 62);
const int MAXN = 5005;

struct Rect {
    long long x, y;
} a[MAXN], b[MAXN];

int n, m;
long long dp[MAXN];

bool cmp_rect(const Rect &lhs, const Rect &rhs) {
    if (lhs.x != rhs.x) {
        return lhs.x < rhs.x;
    }
    return lhs.y > rhs.y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力 DP。
    // 去掉被支配矩形后，直接枚举最后一组从哪里开始分段。
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }

    sort(a + 1, a + n + 1, cmp_rect);

    m = 0;
    for (int i = 1; i <= n; i++) {
        while (m > 0 && b[m].y <= a[i].y) {
            m--;
        }
        b[++m] = a[i];
    }

    dp[0] = 0;
    for (int i = 1; i <= m; i++) {
        dp[i] = INF;
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], dp[j] + b[i].x * b[j + 1].y);
        }
    }

    cout << dp[m] << '\n';
    return 0;
}

关键先做一个预处理。

把矩形按长 x 递增排序；若长相同，则让宽 y 较大的排前面。

如果一个矩形满足：

  • 长不大于另一个矩形
  • 宽也不大于另一个矩形

那么它就是被支配矩形，可以删掉。

删完后，保留下来的矩形满足：

  • x 递增
  • y 递减

这时若最后一组是 (j+1..i)，它的代价就是：

x_i * y_{j+1}

因为这段里最大长一定是最后一个矩形的长，最大宽一定是第一个矩形的宽。

于是得到 DP：

dp[i] = min(dp[j] + x_i * y_{j+1})

这是标准斜率优化形式：

  • 决策点 j 对应一条线
  • 查询点是当前的 x_i

又因为保留下来的 x_i 单调递增、y_{j+1} 单调递减，所以可以用单调队列维护凸包。

DP 转移方程

核心状态：

dp[i] 为前 i 个矩形的最小花费

核心转移：

dp[i]=min(dp[j]+x_i*y_{j+1})

答案收束：

dp[n]

代码

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

const int MAXN = 50005;

struct Rect {
    long long x, y;
} a[MAXN], b[MAXN];

int n, m;
long long dp[MAXN];
int q[MAXN];

bool cmp_rect(const Rect &lhs, const Rect &rhs) {
    if (lhs.x != rhs.x) {
        return lhs.x < rhs.x;
    }
    return lhs.y > rhs.y;
}

long double slope(int i, int j) {
    return (long double) (dp[j] - dp[i]) / (long double) (b[i + 1].y - b[j + 1].y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }

    sort(a + 1, a + n + 1, cmp_rect);

    // 去掉被支配的矩形：
    // 按 x 递增后，只保留 y 严格递减的部分。
    m = 0;
    for (int i = 1; i <= n; i++) {
        while (m > 0 && b[m].y <= a[i].y) {
            m--;
        }
        b[++m] = a[i];
    }

    int head = 1, tail = 1;
    q[1] = 0;
    dp[0] = 0;

    // 约定 b[m + 1].y = 0，方便 slope 中访问 j + 1。
    b[m + 1].y = 0;

    for (int i = 1; i <= m; i++) {
        while (head < tail && slope(q[head], q[head + 1]) <= b[i].x) {
            head++;
        }

        int j = q[head];
        dp[i] = dp[j] + b[i].x * b[j + 1].y;

        while (head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) {
            tail--;
        }
        q[++tail] = i;
    }

    cout << dp[m] << '\n';
    return 0;
}

复杂度

时间复杂度 O(nlogn)O(n log n)，空间复杂度 O(n)O(n)。

总结

这题真正的核心有两步：

  1. 先删掉所有被支配矩形
  2. 再把分组问题化成连续分段 DP

这样斜率优化的结构才会自然出现。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析