农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土
地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000).
每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以
它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3×5的地和一块5×3的地,则他需要
付5×5=25.
FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小
的经费.
题名: acquire
输入格式:
* 第1行: 一个数: N
* 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽
样例输入 (acquire.in):
4
100 1
15 15
20 5
1 100
输入解释:
共有4块土地.
输出格式:
* 第一行: 最小的可行费用.
样例输出 (acquire.out):
500
输出解释:
FJ分3组买这些土地: 第一组:100×1, 第二组1×100, 第三组20×5 和 15×15 plot. 每组
的价格分别为100,100,300, 总共500.
分析：
今天花了点时间把这道题目研究了一下，我觉得这道题目还是有点难度的，O(n^2)的算法很好想也很容易实现，但是50000的数据非得让我想出O(nlogn)的算法。
首先，先用一个显而易见的优化，对于任意一个(xi, yi), 如果存在(xj, yj)满足xi<=xj且yi<=yj, 那么(xi, yi)是完全没有意义的，可以删去。
然后，将所有的地块按x升序排列，因为所有满足第一个优化的地块已经不存在了，所以此时y必然按照降序排列。
容易做出一个O(n^2)的DP，f[i]表示买前i个需要的最小代价, 则有f[i] = min{f[j-1] + yj * xi} (j<=i)
这时候观察状态转移，可以发现这个状态转移是与两个基于j的变量线性相关的。所以，问题就转化为求给出点集所有任意两点连线在y轴截距的最小值，即最小费用。这个问题可以用经典的凸包算法解决，时间复杂度为O(n)，加上排序复杂度O(nlogn)，总的时间复杂度为O(nlogn)。
这个方法可以用接下来我说的方法等价实现：
令j<k, 决策j比决策k优的条件是:
f[j-1] + yj * xi < f[k-1] +yk * xi => (f[k - 1] – f[j - 1]) / (yj – yk) > xi.
令g(j,k) = (f[k-1] – f[j-1]) / (yj – yk) > xi,那个只要用队列维护决策p1 < p2 < p3 .. <pk, 使得g(p1, p2) < g(p2, p3) < … < g(pk-1, pk)即可。
测试数据可以在这里下载。
PS：这个题做得很囧，交到USACO上去AC了，在cena上WA了5个点，世界真是太奇妙了，希望NOIP的时候不要发生这种事情..= =
下面是这题C语言的代码：
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <stdio.h>
#include <stdlib.h>
#define MAX 50005
struct rect { long long w, h; };
struct line {
long long m, b;
line(long long x=0, long long y=0) { m=x; b=y; }
};
int N, lstart, lend;
rect plots[MAX];
long long best[MAX];
line lines[MAX];
int cmp(const void *a, const void *b) {
rect p = *(rect *)a, q = *(rect *)b;
if (p.w < q.w) return -1;
if (p.w > q.w) return 1;
if (p.h < q.h) return -1;
return 1;
}
bool bad(line x, line y, line z) {
// lines x and y intersect at x-coordinate p1
// lines y and z intersect at x-coordinate p2
// bad <--> p1 >= p2
return ((y.m-z.m) * (y.b-x.b) >= (x.m-y.m) * (z.b-y.b));
}
int main() {
FILE *in = fopen("acquire.in", "r");
fscanf(in, "%d", &N);
for (int i = 0; i < N; i++) {
fscanf(in, "%lld%lld", &plots[i].w, &plots[i].h);
}
fclose(in);
qsort(plots, N, sizeof(plots[0]), cmp);
int tN = 0;
for (int i = 0; i < N; i++) {
plots[tN] = plots[i];
while (tN > 0 &&
plots[tN].w >= plots[tN-1].w &&
plots[tN].h >= plots[tN-1].h) {
plots[tN-1] = plots[tN];
tN--;
}
tN++;
}
N = tN;
best[0] = 0;
lines[0] = line(plots[0].h, best[0]);
lstart = 0;
lend = 1;
for (int i = 0; i < N; i++) {
// compute best[i+1]
for (int j = lstart; j < lend; j++) {
long long tmp = lines[j].m * plots[i].w + lines[j].b;
if (j == lstart) {
best[i+1] = tmp;
}
else if (tmp < best[i+1]) {
best[i+1] = tmp;
lstart = j;
}
else {
break;
}
}
if (i < N-1) {
// compute new line
lines[lend] = line(plots[i+1].h, best[i+1]);
lend++;
// erase irrelevant lines
while (lend-lstart >= 3 &&
bad(lines[lend-3], lines[lend-2], lines[lend-1])) {
lines[lend-2] = lines[lend-1];
lend--;
}
}
}
FILE *out = fopen("acquire.out", "w");
fprintf(out, "%lld\n", best[N]);
fclose(out);
return 0;
} |