题目传送门(BZOJ)

题解 :

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

代码 :

#include <map>#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define P(i, j) ((i-1)*m+j)const int N = 1100;#define ll long longll 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<pair<int, int>, int> id;priority_queue<BLOCK> 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原创, 转载必须以链接形式注明>原文链接<