本文共 1903 字,大约阅读时间需要 6 分钟。
For each case, print a single integer, the maximum number of cells in a valid rectangle.
2
2 0 1 2 2 1 3 1 1 3 2 2 3 1 3 2 1 输出 复制 1 4给出一个矩阵, 找到一个子矩阵满足矩阵内任意2元素差不超过M, 求子矩阵的最打的积
枚举上下边界, 同时枚举左边界, 通过单调队列可以确定最大满足题意的右边界
#includeusing namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef long long LL;const int INF = 1 << 30;const int MAXN = 510;int T, n, m, a[MAXN][MAXN];int cmax[MAXN], cmin[MAXN]; //每一列的最大值/最小值int qmin[MAXN], qmax[MAXN], head1, head2, tail1, tail2;int getAns(){ head1 = head2 = tail1 = tail2 = 0; int l = 1, ret = 0; for(int r = 1; r <= n; ++r){ //枚举右边界, 通过单调队列确定左边界 while(head1 < tail1 && cmin[qmin[tail1-1]] > cmin[r]) --tail1; qmin[tail1++] = r; while(head2 < tail2 && cmax[qmax[tail2-1]] < cmax[r]) --tail2; qmax[tail2++] = r; while(head1 < tail1 && head2 < tail2 && cmax[qmax[head2]]-cmin[qmin[head1]] > m){ l = min(qmax[head2], qmin[head1]) + 1; while(head1 < tail1 && qmin[head1] < l) ++head1; while(head2 < tail2 && qmax[head2] < l) ++head2; } ret = max(ret, r-l+1); } return ret;}int main() { scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d",&a[i][j]); int ans = 0; for(int i = 1; i <= n; ++i){ //i, j表示枚举上下界 for(int j = 1; j <= n; ++j) cmax[j] = -1, cmin[j] = INF; for(int j = i; j <= n; ++j){ for(int k = 1; k <= n; ++k){ cmax[k] = max(cmax[k], a[j][k]); cmin[k] = min(cmin[k], a[j][k]); } ans = max(ans, (j-i+1)*getAns()); } } printf("%d\n",ans); } return 0;}
转载地址:http://ldfdf.baihongyu.com/