土地购买（斜率优化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;

}

巴特西

土地购买（斜率优化dp）

土地购买（斜率优化dp）

题目描述

输入格式

输出格式

样例

样例输入

样例输出

样例解释

数据范围与提示

分析

代码

最新文章

热门文章

巴特西

土地购买 （斜率优化dp）

土地购买 （斜率优化dp）

题目描述

输入格式

输出格式

样例

样例输入

样例输出

样例解释

数据范围与提示

分析

代码

最新文章

热门文章

土地购买（斜率优化dp）

土地购买（斜率优化dp）