(贪心5.1.1)POJ 1230 Pass-Muraille

 
/* 
 * POJ_1230.cpp 
 * 
 *  Created on: 2013年10月9日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
  
using namespace std;  
  
int map[105][105];  
  
int main() {  
    int t, n, k, x, y, x1, y1, max_x, max_y, sum_s;  
  
    scanf("%d", &t);  
    while (t--) {  
        max_x = 0;  
        max_y = 0;  
        sum_s = 0;  
        memset(map, 0, sizeof(map));  
  
        scanf("%d%d", &n, &k);  
        int i;  
        for (i = 1; i <= n; ++i) {  
            scanf("%d%d%d%d", &x, &y, &x1, &y1);  
  
            if (x > max_x) {  
                max_x = x;  
            }  
  
            if (x1 > max_x) {  
                max_x = x1;  
            }  
  
            if (y > max_y) {  
                max_y = y;  
            }  
  
            int j;  
            if (x < x1) {  
                for (j = x; j <= x1; ++j) {  
                    map[j][y] = i;  
                }  
            } else {  
                for (j = x1; j <= x; ++j) {  
                    map[j][y] = i;  
                }  
            }  
        }  
  
        for (i = 0; i <= max_x; ++i) {  
            int temp = 0;  
            int j;  
            for (j = 0; j <= max_y; ++j) {  
                if (map[i][j] > 0) {  
                    temp++;  
                }  
            }  
  
            int offset = temp - k;  
            if (offset > 0) {  
                sum_s += offset;  
  
                while (offset--) {  
                    int max_s = 0;  
                    int max_bh = 0;  
                    int k;  
                    for (k = 0; k <= max_y; ++k) {  
                        if (map[i][k] > 0) {  
                            int z;  
                            int temp_s = 0;  
                            for (z = i + 1; z <= max_x; ++z) {  
                                if (map[z][k] == map[i][k]) {  
                                    temp_s++;  
                                } else {  
                                    break;  
                                }  
                            }  
  
                            if (max_s < temp_s) {  
                                max_s = temp_s;  
                                max_bh = k;  
                            }  
                        }  
                    }  
  
                    int a;  
                    for (a = i; a <= i + max_s; ++a) {  
                        map[a][max_bh] = 0;  
                    }  
                }  
            }  
        }  
  
        printf("%d\n", sum_s);  
    }  
  
    return 0;  
}  

补充：软件开发 , C++ ,

上一个：hdu 3966 (树链剖分+线段树)
下一个：rnqoj-57-找啊找啊找GF-二维背包