BZOJ 1597

发表于 |

题目

Famer John准备扩大他的农场，他正在考虑$N$块长方形的土地。每块土地的价格是它的面积，但FJ可以同时购买多快土地。这些土地的价格是它们最大的长乘以它们最大的宽，但是土地的长宽不能交换。如果FJ买一块$3\times 5$的地和一块$5\times 3$的地，则他需要付$5\times 5=25$元。FJ希望买下所有的土地，但是他发现分组来买这些土地可以节省经费。他需要你帮助他找到最小的经费。

数据范围

$1\leq N \leq 50000 \quad 1\leq 长，宽\leq 10^6$

做法

观察到，较小的土地可以在买大土地的时候顺带买（送？）了。于是，将土地按$(w,h)$字典序从小到大排序，将小的土地去掉，类似单调栈的维护。剩下的土地全是按照$w$递增，$h$递减的顺序来排列了。

用反证法，易证，取连续的土地一起买是最优的。

DP方程为:$dp[i]=min_{0≤j<i}(dp[j]+h[j+1]\times w[i]]) $

显然可以斜率优化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int N, deq[MAX_N];
ll h[MAX_N], w[MAX_N], dp[MAX_N];
struct NODE {ll h, w;} node[MAX_N];
inline bool check(int x, int y, int z)
{
	ll bx = h[x], dx = dp[x];
	ll by = h[y], dy = dp[y];
	ll bz = h[z], dz = dp[z];
	return (dy - dx) * (bz - by) <= (dz - dy) * (by - bx);
}
inline ll f(int i, int x)
{
	return dp[i] + h[i] * w[x - 1];
}
bool cmp_xy(const NODE &a, const NODE &b)
{
	if (a.w == b.w) return a.h < b.h;
	return a.w < b.w;
}
void solve()
{
	sort(node, node + N, cmp_xy);
	int top = 0;
	for (int i = 0; i < N; ++i) {
		while (top > 0 && node[i].h >= h[top - 1]) top--;
		w[top] = node[i].w; h[top++] = node[i].h;
	}
	dp[0] = 0;
	deq[0] = 0;
	int s = 0, t = 1;
	for (int i = 1; i <= top; ++i) {
		while (t - s > 1 && f(deq[s], i) >= f(deq[s + 1], i)) s++;
		dp[i] = f(deq[s], i);
		while (t - s > 1 && check(deq[t - 2], deq[t - 1], i)) t--;
		deq[t++] = i;
	}
	printf("%lld\n", dp[top]);
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i) scanf("%lld%lld", &node[i].w, &node[i].h);
	solve();
	return 0;
}