传送门：>HERE<
题意：购买一组土地的费用是最长的长乘以最长的宽。现给出n块土地，求购买所有土地（可以将土地分为任意组，不需按顺序）的最小费用
解题思路
动态规划+斜率优化
斜率优化在这道题里并不难，关键是第一步的方程以及思想
由于买一组土地的关键是最大的长和宽，所以设任意两块土地$x, y$，若$w[x] leq w[y] 且 l[x] leq l[y]$，那么我们可以把$x, y$放在一组里，这样x存不存在都一样。因此x就可以扔掉不管了。所以第一步我们可以把所有没用的都扔掉。
那么怎么扔呢？首先对所有土地以高度为第一关键字，宽度为第二关键字从小到大排序。直接利用单调栈踢出所有没用的土地——然后让每一块土地依次进栈，由于高度是单调递增的，那么如果当前土地的宽度 $geq$ 栈顶的宽度，也就意味着栈顶那块就没用了，因此可以pop
这样做有什么好处？令$f[i]$表示购买前i块土地的费用，枚举断点j，得状态转移方程$$f[i] = f[j] + h[i] * w[j+1]$$由于现在栈内已经单调，根据递增与递减的性质，就可以O(1)求得这一区间土地长宽的最大最小值了
然后就可以做斜率优化的DP了。
Code
long long
坑点挺多的，调了一上午。先是x坐标移项之后是负的，并且栈溢出要判断，不然top减成负数了。
/*By QiXingzhi*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; #define int long long const int MAXN = 50010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } struct Land{ int w,h; }a[MAXN],A[MAXN]; int n,top,h,t,sta[MAXN],q[MAXN],f[MAXN]; inline bool comp(const Land& a, const Land& b){ return (a.h != b.h) ? a.h < b.h : a.w < b.w; } inline double X(int i){ return -A[i+1].w; } inline double Y(int i){ return f[i]; } inline double Slope(int i, int j){ return (double)(Y(i)-Y(j)) / (double)(X(i)-X(j)); } main(){ n = r; for(int i = 1; i <= n; ++i) a[i].w = r, a[i].h = r; sort(a+1, a+n+1, comp); sta[++top] = 1; for(int i = 2; i <= n; ++i){ while(top>0 && a[i].w >= a[sta[top]].w) --top; sta[++top] = i; } for(int i = 1; i <= top; ++i) A[i] = a[sta[i]]; for(int i = 1; i <= top; ++i){ while(h<t && Slope(q[h],q[h+1]) < A[i].h) ++h; f[i] = f[q[h]] + A[q[h]+1].w * A[i].h; while(h<t && Slope(q[t],q[t-1]) > Slope(q[t],i)) --t; q[++t] = i; } printf("%lld", f[top]); return 0; }