首页 > 其他分享 >P2900 [USACO08MAR] Land Acquisition G

P2900 [USACO08MAR] Land Acquisition G

时间:2024-08-28 23:47:23浏览次数:9  
标签:Land int tr P2900 ans using 矩形 id Acquisition

题目

image

思路

我们按照土地的长为第一关键字,土地的宽为第二关键字,从大到小排序,对于将被大矩形完全包含的小矩形删去,因其不影响结果,这样就得到了长严格下降,宽严格上升的序列。

从左往右考虑合并,假如将 \(l\) 到 \(r\) 段合并,那么长取矩形 \(l\) 的长 \(w_l\),宽取矩形 \(r\) 的宽 \(h_r\)。

可以写出转移方程 \(f_i = \min\limits_{j = 0}^{i - 1}\{f_j + h_i \cdot w_j\}\),然后就是转化为 \(y = kx + b\) 的形式,放入李超线段树随便搞就过了。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;
using PII = pair<int, int>;

const int N = 1000010;

int n, cnt;
PII p[N], a[N];

struct func {
    int k, b = 1e18;
};

struct node {
    func id;
} tr[N << 2];

int gety(func id, int x) {
    return id.k * x + id.b;
}

bool compare(func f1, func f2, int x) {
    int y1 = gety(f1, x);
    int y2 = gety(f2, x);
    return y1 < y2;
}

void modify(int u, int l, int r, int pl, int pr, func s) {
    int mid = l + r >> 1;
    if (l > r) return;
    if (pl <= l && r <= pr) {
        if (tr[u].id.b == 1e18) {
            tr[u].id = s;
            return;
        }
        if (compare(s, tr[u].id, mid)) swap(tr[u].id, s);
        if (compare(s, tr[u].id, l)) modify(u << 1, l, mid, pl, pr, s);
        if (compare(s, tr[u].id, r)) modify(u << 1 | 1, mid + 1, r, pl, pr, s);
        return;
    }
    if (pl <= mid) modify(u << 1, l, mid, pl, pr, s);
    if (pr > mid) modify(u << 1 | 1, mid + 1, r, pl, pr, s);
}

int query(int u, int l, int r, int x) {
    int mid = l + r >> 1;
    int ans = gety(tr[u].id, x);
    if (l == r) return ans;
    if (x <= mid) return min(ans, query(u << 1, l, mid, x));
    else return min(ans, query(u << 1 | 1, mid + 1, r, x));
}

int f[N];

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
    sort(p + 1, p + n + 1, greater<PII>());
    for (int i = 1; i <= n; i++) {
        a[++cnt] = p[i];
        int j = i;
        while (j <= n && p[j].first <= p[i].first && p[j].second <= p[i].second) j++;
        i = j - 1;
    }
    n = cnt;
    for (int i = 1; i <= n; i++) p[i] = a[i];
    for (int i = 1; i <= n; i++) {
        modify(1, 1, N - 10, 1, N - 10, {p[i].first, f[i - 1]});
        f[i] = query(1, 1, N - 10, p[i].second);
    }
    cout << f[n] << '\n';
    return 0;
}

标签:Land,int,tr,P2900,ans,using,矩形,id,Acquisition
From: https://www.cnblogs.com/Yuan-Jiawei/p/18385715

相关文章

  • D. Determine Winning Islands in Race
    https://codeforces.com/contest/1998/problem/D思路:求出到达每个点的最短路径,然后从每个点i考虑跳跃到点j(i->j有边),i+1默认为必胜态,则必败态为j-从1~j的步数。如果必败态所在的位置>必胜态,则更新差分数组,最后求和即可。总结:一开始只考虑了从1~j的步数只能是1步1步走的,没考虑......
  • 题解:CF644A Parliament of Berland
    本题题意有\(n\)个议员,编号为\(1\simn\),就坐在\(a\timesb\)的礼堂里,求如何安排座位能够使得任意两个相邻的座位上的议员奇偶性不相同。思路无解情况当\(n>a\timesb\)时,必定无法满足,则直接输出-1。有解情况打表找规律。我们发现,只要让奇数行正着就坐,偶数......
  • 假设Sigmund Landers在商业街设置了一个提供建议的摊位,顾客可以购买1分钟,2分钟,或3分钟
    /假设SigmundLanders在商业街设置了一个提供建议的摊位,顾客可以购买1分钟,2分钟,或3分钟的建议,为确保交通每个摊位前排队等待的顾客最多10人,用两个队列模拟两个摊位/#include<stdio.h>#include<stdlib.h>#defineMAX_SIZE10typedefstruct{intitems[MAX_SIZE];......
  • 【13.PIE-Engine案例——加载Landsat8 Collection2 SR数据集】
    原始链接原始路径欢迎大家登录航天宏图官网查看本案例原始来源结果展示具体代码/***@File:Landsat8Collection2SR*@Time:2021/5/24*@Author:piesat*@Version:1.0*@Contact:400-890-0662*@License:(C)Copyright航......
  • 【15.PIE-Engine案例——加载Landsat 8 SR数据集】
    加载Landsat8SR数据集原始路径欢迎大家登录航天宏图官网查看本案例原始来源最终结果具体代码/***@File:Landsat8SRImages*@Time:2020/7/21*@Author:piesat*@Version:1.0*@Contact:400-890-0662*@License:(C)Copyr......
  • GEE案例:Landsat 5、7、8影像构建1985-2023年rsei生态遥感指数详细代码
    之前关于RSEI的博客 GoogleEarthEngine(GEEÿ......
  • 题解:CF634A Island Puzzle
    CF634AIslandPuzzle题解分析由于我们仅能移动\(0\),所以其它数字的相对顺序较原来应该是不变的,所以我们从环中删除\(0\)再判断相对位置即可。还有需要注意的是本题是一个环,找到末尾需要用取模操作回到开头继续比较。示例代码#include<bits/stdc++.h>usingnamespacest......
  • IDL根据Landsat QA波段去云处理【代码】
    IDL根据LandsatQA波段去云处理【代码】​landsatQA波段(质量评估波段)是Landsat卫星影像数据中的一个特殊波段,他在Landsat5-9的每个产品中都存在。虽然我们常用的Landsat影像数据有B1-B7波段,但QA波段并不是其中之一。它可以反映出云、云阴影、雪等类别的像素,常常应用在影像......
  • QOJ6504 Flower‘s Land 2 题解
    QOJ6504Flower'sLand2题解题目链接:QOJ6504Flower'sLand2题意:给定一个只包含\(0,1,2\)的序列,\(T\)次询问,询问有两种:区间所有数加\(1\)然后模\(3\)求一段区间能否通过每次删掉相邻两个相同的数删完(如\(1,0,0,2,2,1\)就满足条件)题解:考虑用什么方法来维护区间......
  • 如何在 GoLand 中使用 gofmt 和 goimports 工具
    如何在GoLand中使用gofmt和goimports工具参考文章GoLand是JetBrains公司开发的一款Go语言集成开发环境(IDE),拥有丰富的代码自动补全、错误提示和代码重构等功能,极大地提高了编程效率。Go语言有一套自带的代码格式化工具——gofmt,它能够自动将非标准的Go代码格式化为......