本文共 1903 字，大约阅读时间需要 6 分钟。

Input

Output

For each case, print a single integer, the maximum number of cells in a valid rectangle.

Examples

2

Hint

题意:

给出一个矩阵, 找到一个子矩阵满足矩阵内任意2元素差不超过M, 求子矩阵的最打的积

题解:

枚举上下边界, 同时枚举左边界, 通过单调队列可以确定最大满足题意的右边界

经验小结:

#include
   
    using 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;}
   

转载地址：https://suprit.blog.csdn.net/article/details/102644456 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！