【Luogu2900】土地征用（斜率优化，动态规划）

题面

Description

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

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

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

Input

第1行: 一个数: N

第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽

Output

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

Sample Input

4

100 1

15 15

20 5

1 100

Sample Output

500

Hint

输入解释:

共有4块土地.

输出解释:

FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和 15x15 plot. 每组的价格分别为100,100,300, 总共500.

题解

因为土地是可以任意分组的

所以不能够直接搞

所以排序x为第一关键字，y为第二关键字排序之后

显然有一部分的土地是没有必要的

即：\(xi<xj\)并且\(yi<yj\)的土地i是没有必要的

因为我在购买j土地的时候，i一定可以直接包含来里面

所以i是没有意义的土地

所以先搞出\(O(n^{2})\)的暴力

	  for(int i=1;i<=tot;++i)

		  for(int j=0;j<i;++j)

			  f[i]=min(f[i],f[j]+1ll*a[i].x*a[j+1].y);

那么，这样子处理完之后

我们会发现，x是单增的，y是单减的

假设\(j\)的转移优于\(k（j<k）\)

于是就有：

然后随便移一下就可以了

斜率优化直接搞就行啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

using namespace std;

#define MAX 51000

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Node

{

	int x,y;

}la[MAX],a[MAX];

inline bool operator <(Node i,Node j)

{

	if(i.x!=j.x)return i.x<j.x;

	return i.y<j.y;

}

int n,tot,h,t,p[MAX];

long long f[MAX];

double count(int j,int k)

{

	return 1.0*(f[k]-f[j])/(a[j+1].y-a[k+1].y);

}

int main()

{

	n=read();

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

		la[i].x=read(),la[i].y=read();

	sort(&la[1],&la[n+1]);

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

	{

		while(tot&&a[tot].y<la[i].y)--tot;

		++tot;

		a[tot].x=la[i].x;

		a[tot].y=la[i].y;

	}

	//保证x和y都是单调的

	//f[i]=min{f[j]+a[i].x*a[j].y}

	for(int i=1;i<=tot;++i)f[i]=1e18;

	/*

	  for(int i=1;i<=tot;++i)

		  for(int j=0;j<i;++j)

			  f[i]=min(f[i],f[j]+1ll*a[i].x*a[j+1].y);

	*/

	for(int i=1;i<=tot;++i)

	{

		while(h<t&&count(p[h],p[h+1])<=a[i].x)h++;

		int gg=p[h];

		f[i]=f[gg]+1ll*a[i].x*a[gg+1].y;

		while(h<t&&count(p[t-1],p[t])>=count(p[t-1],i))t--;

		p[++t]=i;

	}

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

	return 0;

}