关键词：
[Usaco2008 Mar]土地购买
Time Limit: 10 Sec Memory Limit: 162 MB
Description
农夫John准备扩大他的农场,他正在考虑\(N (1 <= N <= 50,000)\)块长方形的土地. 每块土地的长宽满足\((1 <= 宽 < = 1,000,000; 1 <= 长 <= 1,000,000)\). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价
格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块\(3*5\)的地和一块\(5*3\)的地,则他需要
付\(5*5=25\). FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.
- 第1行: 一个数:$ N$
第\(2..N+1\)行: 第\(i+1\)行包含两个数,分别为第\(i\)块土地的长和宽
Output
第一行: 最小的可行费用.
4
100 1
15 15
20 5
1 100
Sample Output
500
输入解释:
共有4块土地.
FJ分3组买这些土地:
第一组:100x1,
第二组1x100,
第三组20x5 和 15x15 plot.
每组的价格分别为100,100,300, 总共500.
显然有些田是白送的2333.。。。。（只要存在有别的田比这块田的长和宽都大，那么这块田直接白送。。。。。对吧）
然后把这些直接去掉。。。。
由于事先已经知道是斜率优化。。。（提示太明显了。。感觉刷专题就这一点不怎么好。。。）
我们就去凑那个式子
先按x从小到大排序。。。因为已经去掉了不用的土地，那么此时的y一定就是从大到小排的序
\(dp[i]\)表示买前\(i\)块土地的最优解，所以有了状态转移方程方程：
\(dp[i] = dp[j] + x[i] * y[j+1]\)
写成一次函数的形式：
\(-dp[j]=y[j+1]*x[i]-dp[i]\)
所以每一个点就是\((y[j+1],-dp[j])\)
\(k=x[i]\)满足单调性
当然这里就差不多了，但是由于上一篇我说的不是很清楚，我想再多说一句。。。
最开始排除的是两个点的斜率小于\(k\)的，其实是因为画图可以看出后面的点答案一定优于前面的。而当斜率大于k时，虽然当前的答案时前面的点更好（所以计算答案的时候就用的是第一个满足条件的点），但是由于\(k\)在单增，有可能\(k\)会超过它的斜率，所以蹦年确定。
而倒着删是因为如果不是个下凸包形状的话，那么中间那个点一定不是最优点，要么它前面的那个点是最优的，要么后面的是最优的。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
struct lpl
long long x, y;
lin, ini[maxn], field[maxn], point[maxn];
int n, tot, cnt, head, tail;
long long dp[maxn];
inline bool cmp(lpl a, lpl b)
return a.x == b.x ? a.y < b.y : a.x < b.x;
inline void putit()
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lld%lld", &ini[i].x, &ini[i].y);
inline double slop(lpl a, lpl b)
return (double)(a.y - b.y) / (a.x - b.x);
inline void workk()
sort(ini + 1, ini + n + 1, cmp);
for(int i = 1; i <= n; i++)
while(tot && ini[i].y >= field[tot].y) tot--;
field[++tot] = ini[i];
point[head].x = field[1].y; point[head].y = 0;
for(int i = 1; i <= tot; ++i)
while(head < tail && slop(point[head], point[head + 1]) < field[i].x) head++;
dp[i] = (-point[head].y) + field[i].x * point[head].x;
lin.x = field[i + 1].y, lin.y = (-dp[i]);
while(head < tail && slop(point[tail], point[tail - 1]) > slop(point[tail], lin)) tail--;
point[++tail] = lin;
cout << dp[tot];
int main()
putit();
workk();
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可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但... 查看详情