SGi's Blog

A long run.

土地购买(acquire)

类归于： Informatics — SGi at 2:58 下午 on 星期天, 九月 7, 2008

农夫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语言的代码：

?View Code 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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#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 &lt; q.w) return -1;
  if (p.w &gt; q.w) return 1;
  if (p.h &lt; 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 &lt;--&gt; p1 &gt;= p2
  return ((y.m-z.m) * (y.b-x.b) &gt;= (x.m-y.m) * (z.b-y.b));
}
 
int main() {
  FILE *in = fopen("acquire.in", "r");
  fscanf(in, "%d", &amp;N);
  for (int i = 0; i &lt; N; i++) {
    fscanf(in, "%lld%lld", &amp;plots[i].w, &amp;plots[i].h);
  }
  fclose(in);
 
  qsort(plots, N, sizeof(plots[0]), cmp);
  int tN = 0;
  for (int i = 0; i &lt; N; i++) {
    plots[tN] = plots[i];
    while (tN &gt; 0 &amp;&amp; 
	   plots[tN].w &gt;= plots[tN-1].w &amp;&amp; 
	   plots[tN].h &gt;= 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 &lt; N; i++) {
    // compute best[i+1]
    for (int j = lstart; j &lt; lend; j++) {
      long long tmp = lines[j].m * plots[i].w + lines[j].b;
      if (j == lstart) {
	best[i+1] = tmp;
      }
      else if (tmp &lt; best[i+1]) {
	best[i+1] = tmp;
	lstart = j;
      }
      else {
	break;
      }
    }
 
    if (i &lt; N-1) {
      // compute new line
      lines[lend] = line(plots[i+1].h, best[i+1]);
      lend++;
 
      // erase irrelevant lines
      while (lend-lstart &gt;= 3 &amp;&amp; 
	     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;
}