BZOJ 4165: 矩阵 – [堆]


题目传送门(BZOJ)

题解 :

如果你做过 NOI2010 超级钢琴的话, 这道题就非常简单了
由于保证权值非负, 所以我们先把所有 minA \times minB 大小的矩阵扔到堆里,
这个堆是一个小根堆
定义一个矩阵小于另一个为它的权值和小于另一个, 我们可以预处理矩阵前缀和求这个
每次弹出堆顶, 在所有还未被删除的矩阵中, 这个堆顶一定是最小的,
因为在堆中的矩阵一定比它大, 而不在堆中的, 要么被删除了, 要么可以通过当前堆中的矩阵扩大获得, 一定比当前堆中矩阵大
对于这个堆顶, 我们分别把它向左/向上/向右/向下扩大一行, 把这四个扔到堆里, 请注意,
由于一个矩阵可能由几个不同的其他矩阵扩充得到, 所以要判断一下之前是否出现过, 用 map 即可
另外, 若你的堆是重载小于号实现的, 在用 map 的时候千万不要用这个小于号,
否则被判重的就不是矩阵, 而是矩阵权值和了. 我们把左上角和右下角做个 pairmap 里就行
重复这样的操作 k-1 次, 之后的堆顶就是答案矩阵

代码 :

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define P(i, j) ((i-1)*m+j)
const int N = 1100;
#define ll long long
ll s[N][N];
struct BLOCK {
    BLOCK(int _x1 = 0, int _y1 = 0, int _x2 = 0, int _y2 = 0) :
    x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}
    int x1, y1, x2, y2;
    inline ll getSum() const {
        return s[x2][y2]-s[x1-1][y2]+s[x1-1][y1-1]-s[x2][y1-1];
    }
    bool operator < (const BLOCK &A) const {
        return getSum() > A.getSum();
    }
};
map, int> id;
priority_queue q;
int n, m, A, B, K;
inline void push(const BLOCK &A) {
    int x1 = A.x1, y1 = A.y1, x2 = A.x2, y2 = A.y2;
    if(x1 > 1 && !id[make_pair(P(x1-1, y1), P(x2, y2))]) q.push(BLOCK(x1-1, y1, x2, y2)), id[make_pair(P(x1-1, y1), P(x2, y2))] = 1;
    if(y1 > 1 && !id[make_pair(P(x1, y1-1), P(x2, y2))]) q.push(BLOCK(x1, y1-1, x2, y2)), id[make_pair(P(x1, y1-1), P(x2, y2))] = 1;
    if(x2 < n && !id[make_pair(P(x1, y1), P(x2+1, y2))]) q.push(BLOCK(x1, y1, x2+1, y2)), id[make_pair(P(x1, y1), P(x2+1, y2))] = 1;
    if(y2 < m && !id[make_pair(P(x1, y1), P(x2, y2+1))]) q.push(BLOCK(x1, y1, x2, y2+1)), id[make_pair(P(x1, y1), P(x2, y2+1))] = 1;
}
int main() {
    scanf("%d%d%d%d%d", &n, &m, &A, &B, &K);
    for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) {
        ll x; scanf("%lld", &x);
        s[i][j] = s[i-1][j]-s[i-1][j-1]+s[i][j-1]+x;
    }
    for(int i = 1; i+A-1 <= n; i ++ ) for(int j = 1; j+B-1 <= m; j ++ ) {
        q.push(BLOCK(i, j, i+A-1, j+B-1));
    }
    for(int i = 1; i < K; i ++ ) {
        if(q.empty()) return puts("-1"), 0;
        BLOCK u = q.top(); q.pop();
        push(u);
    }
    if(q.empty()) return puts("-1"), 0;
    printf("%lld\n", q.top().getSum());
    return 0;
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注