【洛谷 P2900】 [USACO08MAR]土地征用Land Acquisition（斜率优化，单调栈）

题目链接
双倍经验
设(H)表示长，(W)表示宽。
若(H_i<H_j)且(W_i<W_j)，显然(i)对答案没有贡献。
于是把所有点按(H)排序，然后依次加入一个按(W)降序排序的单调栈。
这个单调栈里就是一定对答案有贡献的点，现在的问题就是把这些点分段，使总费用最小。
设(f[i])表示前(i)块土地的最小费用。
然后枚举断点(0<=j<i)，则(f[i]=min(f[j]+W_{j+1}*H_i))
斜率优化搞一搞就行了。

// f[i] = f[j] + x[i] * y[j + 1]
// f[j] = -x[i] * y[j + 1] - f[i]

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 50010;
#define ll long long
inline ll min(const ll a, const ll b){
	return a < b ? a : b;
}
int n, top; 
struct point{
	int x, y;
	int operator < (const point A) const{
		return x != A.x ? x < A.x : y < A.y;
	}
}a[MAXN], st[MAXN];
int q[MAXN], head, tail;
ll f[MAXN];
inline double k(int i, int j){
	return (f[i] - f[j]) / (st[i + 1].y - st[j + 1].y);
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	   scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; ++i){
		while(top && st[top].y <= a[i].y) --top;
		st[++top] = a[i];
	}
	for(int i = 1; i <= top; ++i){
	   while(head < tail && k(q[head], q[head + 1]) > -st[i].x) ++head;
	   int j = q[head];
	   f[i] = f[j] + (ll)st[i].x * st[j + 1].y;
	   while(head < tail && k(q[tail - 1], q[tail]) <= k(q[tail], i)) --tail;
	   q[++tail] = i;
    }
    printf("%lld
", f[top]);
    return 0;
}