POJ 2703 - Maximum Area Covered by Rectangles

http://poj.org/problem?id=2703

概要

この問題では長方形の「幅」を「長さが短い方の辺」と定義し、「高さ」を「長さが長い方の辺」と定義する。 \(N\) 個の長方形が与えられるので、これを左下の頂点が原点になるようにして縦方向か横方向に置いていったとき、 全体でカバーしている面積の最大値を答える。

制約

• \(2 \le N \le 1000\)
• 「幅」が等しい長方形は15個以下
• 「幅」が異なる長方形ならば、片方の長方形がもう片方を含むことはない。つまり例えば \(4 \times 6\) の長方形と \(5 \times 7\) の長方形の両方が存在するようなことはない。

解法

縦方向か横方向の2種類の置き方しかないので、「幅」が同じ場合は「高さ」が高いほうから2つまでしか使うことはない。

最後の制約が重要。 この制約により、ある長方形を新たに置いたときに必ず全体の面積は増える。 よって、「幅」の小さいほうから順に並べていき、縦方向がいくつまでいったか・横方向がいくつまでいったかをキーとして DP すればいい。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct rect
 6 {
 7   int w, h;
 8   bool operator<(const rect& r) const
 9   {
10     if (w == r.w) {
11       return h > r.h;
12     } else {
13       return w < r.w;
14     }
15   }
16 };
17 
18 int main()
19 {
20   int N;
21   while (scanf("%d", &N) != EOF && N != -1) {
22     static rect v[1001];
23     v[0].w = v[0].h = 0;
24     for (int i = 1; i <= N; i++) {
25       scanf("%d %d", &v[i].w, &v[i].h);
26     }
27     sort(v, v+N+1);
28 
29     static int dp[1001][1001];
30     for (int i = 0; i <= N; i++) {
31       fill_n(dp[i], N+1, 0);
32     }
33 
34     int ans = 0;
35     for (int i = 0; i < N; i++) {
36       for (int j = 0; j < N; j++) {
37         const int k = max(i, j) + 1;
38         // put vertical
39         dp[k][j] = max(dp[k][j], dp[i][j] + (v[k].w-v[i].w) * (v[k].h-v[j].w));
40         // put horizontal
41         dp[i][k] = max(dp[i][k], dp[i][j] + (v[k].h-v[i].w) * (v[k].w-v[j].w));
42         if (k == N) {
43           ans = max(ans, dp[k][j]);
44           ans = max(ans, dp[i][k]);
45         }
46       }
47     }
48     printf("%d\n", ans);
49   }
50   return 0;
51 }