Skip to content

11246: 【原1246】pyramid

题目

题目描述

author: cheezer 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1246

Description

Jaguar 国王在一场战役大胜后决定建造一个金字塔,一方面作为纪念战争胜利的纪念碑,同时亦用作埋葬在战斗中阵亡将士们的墓地。该金字塔将建在战场的所在地,有一个a列b行的矩形底部。在金字塔的底层内将有一个较小的c列d行的矩形墓室,用来存放阵亡将士们的遗体以及他们所用过的武器。

国王的建筑师将该战场分为m列n行小方格的网格。每个小方格的高度用一个整数表示。

金字塔及其内部的墓室均应覆盖网格的完整的小方格,而且其边必须与战场的边平行。

金字塔内墓室小方格的高度必须保持原有的高度不变,但金字塔底部的其余地面则需要平整,平整的方法是将高度较高的小方格内的砂土移到较低的小方格内,这样一来,金字塔底部的最后高度将是底部所覆盖的所有小方格(墓室小方格除外)高度的平均值。建筑师有权选择墓室在金字塔内的位置,但墓室四周要有至少一小方格厚度的墙围绕。

建筑师希望在战场上找到一块最佳的位置来建造该金字塔及其内部的墓室,使得对于给定大小的金字塔,其底部的高度尽可能高。

1246

图中所示是一个战场的例子,每个小方格内的整数表示该格所处区域内的高度。灰色部份表示金字塔的底部,灰色部份所包围的白色部份则表示墓室的位置。该图给出了一个最佳位置。

对于给定尺寸的战场、金字塔和墓室大小以及战场上所有小方格的高度,请编写一程序找出建造金字塔及其墓室的最佳位置,使得金字塔底部的高度为最高。 数据保证存在唯一解。

Input Format

第一行:共有6个以空格分开的正整数,它们顺次分别为:m, n, a, b, c 及 d。

随后n行:每行有m个用空格分开的整数,每行表示一横行小方格的高度。其中,第一行表示战场小方格最上面的一行(第一行),而最后一行表示最下面的一行(第n行)。每行的m个整数依次表示该行上从第一列开始的小方格的高度。

70%: 3 <= n, m <= 10;

80%: 3 <= n, m <= 100;

100%: 3<= n, m <= 1000; 3 <= a <= m, 3 <= b <= n; 1 <= c, d <= a - 2, b - 2; 1 <= h <= 100

Output Format

第一行:必须输出两个由空格分隔的整数,它们表示金字塔的底部的左上角位置,其中第一个整数代表列的坐标,而第二个整数则代表行的坐标。

第二行:必须输出两个由空格分隔的整数,它们表示金字塔内部的墓室的左上角位置,其中第一个整数表示列的坐标,而第二个数字则表示行的坐标。

Sample Input

8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2

Sample Output

4 1
6 2

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1246.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, a, b, c, d;
int sum[1005][1005] = {0};
int dt[1005][1005];
int res[1005][1005] = {0}, q[1005][2], hd, tl;
void init(){
    m = read(), n = read(), a = read(), b = read(), c = read(), d = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            sum[i][j] = sum[i][j - 1] + read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            sum[i][j] += sum[i - 1][j];
    for (int i = d + 1; i < n; ++i){
        hd = tl = 0;
        for (int j = c + 1; j < m; ++j){
            int tt = sum[i][j] - sum[i - d][j] - sum[i][j - c] + sum[i - d][j - c];
            dt[i][j] = tt;
            while (tl > hd && q[tl - 1][1] >= tt)
                --tl;
            q[tl][0] = j, q[tl++][1] = tt;
            if (q[hd][0] <= j - (a - c - 1))
                ++hd;
            res[i][j] = q[hd][1];
        }
    }
}
void solve(){
    int ansx, ansy, ans = INT_MIN, ans_in;
    /* for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j)
            cout << res[i][j] << " ";
        cout << endl;
    } */
    for (int j = c + 1; j < m; ++j){
        hd = tl = 0;
        for (int i = d + 1; i < n; ++i){
            while (tl > hd && q[tl - 1][1] >= res[i][j])
                --tl;
            q[tl][0] = i, q[tl++][1] = res[i][j];
            if (q[hd][0] <= i - (b - d - 1))
                ++hd;
            if (i + 1 >= b && j + 1 >= a){
                int sm = sum[i + 1][j + 1] - sum[i + 1 - b][j + 1] - sum[i + 1][j + 1 - a] + sum[i + 1 - b][j + 1 - a];
                sm -= q[hd][1];
                if (sm > ans) ans = sm, ansx = i + 1, ansy = j + 1, ans_in = q[hd][1];
            }
        }
    }
    ansx -= b - 1, ansy -= a - 1;
    // cout << ansx << " " << ansy << " " << ans_in << endl;
    for (int i = d; i < b - 1; ++i)
        for (int j = c; j < a - 1; ++j){
            if (ans_in == dt[i + ansx][j + ansy]){
                printf("%d %d\n%d %d\n", ansy, ansx, ansy + j - c + 1, ansx + i - d + 1);
                return ;
            }
        }
}
int main(){
    init();
    solve();
    return 0;
}