土地购买（斜率优化dp）

题目描述

农夫 $John$ 准备扩大他的农场,他正在考虑$ N(1 \leqslant N \leqslant 50,000)$ 块长方形的土地. 每块土地的长宽满足$(1 \leqslant$ 宽 $\leqslant 1,000,000; 1 \leqslant$ 长 $\leqslant 1,000,000)$.

每块土地的价格是它的面积,但 $FJ$ 可以同时购买多块土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果 $FJ$ 买一块 $3\times 5$ 的地和一块 $5\times 3$的地,则他需要付 $5\times 5=25$.

$FJ$ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

输入格式

第 $1$ 行：一个数: $N$

第 $2..N+1$ 行：第 $i+1$ 行包含两个数，分别为第 $i$ 块土地的长和宽。

输出格式

第一行: 最小的可行费用。

样例

样例输入

4

100 1 15 15 20 5 1 100

样例输出

样例解释

共有 $4$ 块土地，$FJ$ 分 $3$ 组买这些土地: 第一组: $100\times 1$, 第二组 $1\times 100$ , 第三组 $20\times 5$ 和 $15\times 15$ 每组的价格分别为 $100,100,300$ , 总共 $500$。

数据范围与提示

对于 $50\%$ 的数据 $n \leqslant 1000$

对于 $100\%$ 的数据 $n \leqslant 50000$

数据有一定梯度

分析

题目中说选一堆土地的时候，只用最大的长和宽计算价值，那么我们可以先去重，也就是让包含的关系先处理掉，按照长度从小到大排序，利用一个单调栈来维护单调减的一堆序列，这样就去完了重（所谓的去重），这时候长度就是递增，宽度递减，那么我们只需要取一段区间的端点即可，转化成状态转移方程就是：

\[f[i]\ =\ min(f[i],f[j-1] + len_j \times width_i)
\]

转化一下柿子，变成 $f[j-1] = f[i] - len_j \times width_i$

最后这个式子就可以用来斜率优化了。

代码

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

const int L=1<<20;

char buffer[L],*S,*T;

#define lowbit(x) (x & -x)

#define getchar() (S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T)?EOF:*S++)

#define inline __inline__ __attribute__((__always_inline__))

#define max(a,b) (a>b?a:b)

#define re register

#define ll long long

const int maxn = 5e4+10;

ll f[maxn];

struct Node{

	ll w,l;

}jl[maxn];

ll staw[maxn];

int top;

ll stal[maxn];

ll q[maxn];

ll a[maxn],b[maxn];

inline ll read(){

	int s = 0,f = 1;

	char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-')f = -1;

		 ch = getchar();

	}

	while(isdigit(ch)){

		s = s * 10 + ch - '0';

		ch = getchar();

	}

	return s * f;

}

inline bool cmp(Node a,Node b){//排序

	if(a.l == b.l)return a.w < b.w;

	return a.l < b.l;

}

inline ll calc(int a,int b){//计算函数值

	return f[b] + staw[b+1] * stal[a];

}

inline bool jud(int x1,int x2,int x3){//计算斜率

	return (b[x3] - b[x1]) * (a[x2] - a[x1]) >= (b[x2] - b[x1]) * (a[x3] - a[x1]);

}

signed main(){

	freopen("A.in","r",stdin);

	freopen("A.out","w",stdout);

	re ll n = read();

	for(re int i = 1;i <= n;++i){

		jl[i].w = read();

		jl[i].l = read();

	}

	sort(jl+1,jl+n+1,cmp);

	for(re int i = 1;i <= n;++i){//单调栈去重，找出包含的情况

		while(top && jl[i].w >= staw[top])top--;

		staw[++top] = jl[i].w;

		stal[top] = jl[i].l;

	}

	re int head = 1,tail = 1;

	a[0] = staw[1];

	for(re int i = 1;i <= top;++i){//单调队列斜率优化

		while(head < tail && calc(i,q[head]) >= calc(i,q[head+1]))head++;

		f[i] = calc(i,q[head]);

		a[i] = staw[i + 1];

		b[i] = f[i];

		while(head < tail && jud(q[tail-1],q[tail],i))tail--;

		q[++tail] = i;

	}

	printf("%lld\n",f[top]);

	return 0;

}

土地