[文章目录]
Description
农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费
斜率优化DP，先将能完全覆盖的农田去除，然后发现农场的x递增，y递降。
dp[i]表示前i个农场的最小花费。
dp[i]=dp[j]+y[j]*x[i]（0<=j<=i-1）
然后发现y[j]是递减的，x[i]是递增的，符合条件。
搞一下就出来了，哈哈。
发现一个捷径，第一个while直接代入解析式判断。
第二个，嘿嘿嘿，因为判断交点是有分母的，所以要判断分母的正负，考虑变号。
我们知道k是单调的，但是并不知道是怎么单调的，那？？？
所有分母都是后者-前者的形式，所以，两边同乘分母时直接不变号。
然后，斜率优化需要注意上帝视角是在下面还是上面，k恒正还是恒负。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
int n,tail,h,t;
struct node
{
LL x,y;
}a[500100];
bool cmp(node x,node y)
{
return x.x==y.x ? x.y<y.y : x.x<y.x;
}
LL dp[500100];
int q[500100];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
while(tail&&a[tail].y<=a[i].y) tail--;
a[++tail]=a[i];
}
for(int i=1;i<=tail;i++)
{
while(h<t&&a[q[h]+1].y*a[i].x+dp[q[h]]>=a[q[h+1]+1].y*a[i].x+dp[q[h+1]]) h++;
dp[i]=dp[q[h]]+a[i].x*a[q[h]+1].y;
while(h<t&&(dp[i]-dp[q[t]])*(a[q[t-1]+1].y-a[q[t]+1].y)<=(dp[q[t]]-dp[q[t-1]])*(a[q[t]+1].y-a[i+1].y)) t--;
q[++t]=i;
}
printf("%lld",dp[tail]);
return 0;
}