最省納智捷1年新車83萬起來自星星的你也會打廣告?攝影界美人正妹指定相機款籌400萬醫藥費 俞嫻...
2012-05-16 08:58:38 人氣(103) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][DP最大矩形] 10667 - Largest Block

0
收藏
0
推薦

  Largest Block  

The Problem

Consider a n x n chessboard. The term block(r1,c1,r2,c2) denotes the rectangular subset of squares defined by the intersection of rows {r1,r1+1,...,r2} and columns {c1,c1+1,...,c2}.

There are several occupied blocks on the board. We are interested in the largest block (in the sense of maximum area) that can be placed in the free space remaining in the board.

For example, in a chessboard of size 10, if block(2,2,5,3), block(8,3,9,7), and block(3,6,3,8) represent occupied space, then the largest block that can be placed in free space has area 28. This can be visually checked in the following figure:

r\c 1 2 3 4 5 6 7 8 9 10

1











2


X X






3


X X

X X X

4


X X   o   o   o   o   o   o   o

5


X X   o   o   o   o   o   o   o

6




  o   o   o   o   o   o   o

7




  o   o   o   o   o   o   o

8



X X X X X


9



X X X X X


10











We are interested only in the area of the largest free block, and not in its particular location. Therefore, each instance of the problem has a unique solution.

The Input

The program first reads the number p of instances of the problem. Each instance is described by the size s of the board, the number b of blocks of occupied space, and the vertices r1,c1,r2,c2, of each block:

p number of problem instances in the file
s (board size) instance #1
b (number of blocks)
r1 c1 r2 c2 (first block)
r1 c1 r2 c2 (second block)
... ...
r1 c1 r2 c2 (n-th block)
s (board size) instance #2
b (number of blocks)
r1 c1 r2 c2 (first block)
r1 c1 r2 c2 (second block)
... ...
r1 c1 r2 c2 (n-th block)
... ... instance #p

Assumptions:

  • 1 <= s <= 100
  • 0 <= b <= 100
  • 1 <= r1 <= r2 <=s
  • 1 <= c1 <= c2 <=s
  • Occupied blocks may overlap.

The Output

For each test case the output consists of a integer indicating the area of the largest block that can be located in the available free squares.

Sample Input

3
10
3
2 2 5 3
8 3 9 7
3 6 3 8
20
1
1 1 1 1
10
2
5 1 5 10
1 5 10 5

Sample Output

28
380
25

最大矩形, DP O(n*n*n)

#include <stdio.h>

int main() {
    int p, s, b;
    int r1, r2, c1, c2, i, j, k;
    scanf("%d", &p);
    while(p--) {
        scanf("%d %d", &s, &b);
        char map[101][101] = {};
        while(b--) {
            scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
            for(i = r1; i <= r2; i++)
                for(j = c1; j <= c2; j++)
                    map[i][j] = 1;
        }
        int length, width, tmp = 0, ans = 0;
        for(i = 1; i <= s; i++) {
            int sum[101] = {};
            for(j = i; j <= s; j++) {
                for(k = 1; k <= s; k++) {
                    sum[k] += !map[j][k];
                    if(k == 1 || tmp != length*width)
                        tmp = 0, length = 0;
                    tmp += sum[k];
                    length++, width = j-i+1;
                    if(tmp == length*width) {
                        if(tmp > ans)
                            ans = tmp;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

10667Largest BlockDP
台長:Morris
人氣(103) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 11703 - sqrt log sin
此分類上一篇:[UVA] 496 - Simply Subsets

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文