bzoj1597:[usaco2008mar]土地购买斜率优化

关键词：

Description

Input

Output

Sample Input

Sample Output

HINT

题解：

　　按照X排序， 手动删掉一些无影响的选择

　　剩下的都是 X增大，Y减小的矩阵

　　那么答案必须是选择一段连续的矩阵了

　　这个时候就可以DP

　　他是有单调性的

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
const int N = 1e5+10, inf = 1e9, mod = 1e9+7;
struct ss{
    LL x,y;
}Q[N],tmp[N];
int cmp1(ss s1,ss s2) {
    if(s1.x == s2.x) return s1.y < s2.y;
    else return s1.x < s2.x;
}
int cmp2(ss s1,ss s2) {
    if(s1.y == s2.y) return s1.x < s2.x;
    else return s1.y < s2.y;
}
int n,q[N];
LL dp[N];
int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld%lld",&Q[i].x,&Q[i].y);
    }
    sort(Q+1,Q+n+1,cmp1);
    int cnt = 0;
    for(int i = 1; i <= n; ++i) {
        while(cnt && tmp[cnt].y<=Q[i].y)cnt--;
        tmp[++cnt] = Q[i];
    }
    n = cnt;
    for(int i = 1; i <= n; ++i) Q[i] = tmp[i],dp[i] = 1e15;
    dp[0] = 0;
    int l = 1,r = 2;q[1] = 0;
    q[2] = 1;dp[1] = 1LL*Q[1].x * Q[1].y;
    for(int i = 2; i <= n; ++i) {
        while(l < r && dp[q[l+1]] - dp[q[l]] < 1LL*(Q[q[l]+1].y - Q[q[l+1]+1].y) * Q[i].x) ++l;
        dp[i] = dp[q[l]] + 1LL*Q[i].x * Q[q[l]+1].y;
        while(l < r && (dp[q[r]]-dp[q[r-1]]) * 1LL*(Q[q[r]+1].y-Q[i+1].y) > (dp[i] - dp[q[r]]) * (Q[q[r-1]+1].y-Q[q[r]+1].y)) --r;
        q[++r] = i;
    }
    printf("%lld
",dp[n]);
    return 0;
}

bzoj1597:[usaco2008mar]土地购买斜率优化

1597:[Usaco2008Mar]土地购买TimeLimit: 10Sec  MemoryLimit: 162MBDescription农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价 查看详情

bzoj1597:[usaco2008mar]土地购买斜率优化+凸包维护

1597:[Usaco2008Mar]土地购买TimeLimit:10Sec  MemoryLimit:162MBSubmit:4989  Solved:1847[Submit][Status][Discuss]Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1< 查看详情

bzoj1597:[usaco2008mar]土地购买

【传送门：BZOJ1597】简要题意：　　给出n块土地，给出每块土地的长和宽，可以将n块土地分成若干组，每一组的费用是组中的长最大的土地的长与宽最大的土地的宽的乘积，求出将n块分成若干组的最小费用题解：　　首先我们... 查看详情

[bzoj1597][usaco2008mar]土地购买

...备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但... 查看详情

bzoj1597[usaco2008mar]土地购买

...备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但... 查看详情

bzoj1597[usaco2008mar]土地购买

【算法】DP+斜率优化【题意】n(n≤50000)块土地，长ai宽bi，可分组购买，每组代价为max(ai)*max(bi)，求最小代价。【题解】斜率优化：http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html因为对于土地x和y，若满足a[x]<=a[y]&&b[x]<... 查看详情

bzoj1597:[usaco2008mar]土地购买

式子显然随便搞搞就行，，而且可以先把这些矩形排序，然后如果有比当前矩形x和y都大的矩形，这个矩形是可以忽略的。1#include<bits/stdc++.h>2#defineLLlonglong3#definelowbit(x)x&(-x)4#defineinf0x3f3f3f3f5#defineeps1e-56#defineN1000057usingnamespa... 查看详情

bzoj1597usaco2008mar土地购买斜率优化dp

题目：题目在这里思路与做法:这题如果想要直接dp的话不太好处理。不过，我们发现如果\(a[i].x>=a[j].x\)且\(a[i].y>=a[j].y\)\((\)a是输入的数组，x为长，y为宽\()\)，j是没用的，可以直接去掉，然后就可以dp了容易得出状态转移方... 查看详情

1597:[usaco2008mar]土地购买

1597:[Usaco2008Mar]土地购买TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 4023  Solved: 1470[Submit][Status][Discuss]Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,00 查看详情

bzoj1597

【bzoj1597】[Usaco2008Mar]土地购买2014年5月18日3,0421Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购... 查看详情

bzoj1597[usaco2008]土地购买

...备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但... 查看详情

bzoj1597斜率dp

1597:[Usaco2008Mar]土地购买TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 5115  Solved: 1897[Submit][Status][Discuss]Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,00 查看详情

[usaco2008mar]土地购买(代码片段)

...geOnline/problem.php?id=1597[算法]    首先将所有土地按长为第一关键字，宽为第二关键字排序    显然，当i>j,且yi>=yj时，土地j没有用，不妨使用单调栈弹出所有没有用的土地    用fi表... 查看详情

土地并购(landacquisition,usaco2008mar)

题目描述FarmerJohnisconsideringbuyingmorelandforthefarmandhashiseyeonN(1<=N<=50,000)additionalrectangularplots,eachwithintegerdimensions(1<=width_i<=1,000,000;1<=length_i<=1,000,000).IfF 查看详情

bzoj1597土地购买

...roblem.php?id=1597 (题目链接)题意　　购买n个矩形，每块土地的价格是它的面积，但可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽，求最少花费。Solution　　按照x单增，y单减排序，将可以相互包含的... 查看详情

[bzoj1617][usaco2008mar]rivercrossing渡河问题

1617:[Usaco2008Mar]RiverCrossing渡河问题TimeLimit:5Sec  MemoryLimit:64MBSubmit:1102  Solved:801[Submit][Status][Discuss]DescriptionFarmerJohn以及他的N(1<=N<=2,500)头奶牛打算过一条河，但他们所有的渡河工 查看详情

[bzoj]1616:[usaco2008mar]cowtravelling游荡的奶牛

1616:[Usaco2008Mar]CowTravelling游荡的奶牛TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 1312  Solved: 736[Submit][Status][Discuss]Description奶牛们在被划分成N行M列(2<=N<=100 查看详情

土地购买（bzoj1597）

...备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但... 查看详情