链接：https://ac.nowcoder.com/acm/contest/883/F
来源：牛客网
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
The semester is finally over and the summer holiday is coming. However, as part of your university's graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.
To simplify the problem, let's represent the mountain where trees are to be planted with an N×NN \times NN×N grid. Let's number the rows 1\ 1 1 to N\ N N from top to bottom, and number the columns 1\ 1 1 to N\ N N from left to right. The elevation of the cell in the i\ i i-th row and j\ j j-th column is denoted by ai,ja_{i,j}ai,j. Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2), then the condition ∣ai,j−ak,l∣≤M|a_{i,j} - a_{k,l}| \le M∣ai,j−ak,l∣≤M must hold for x1≤i,k≤x2, y1≤j,l≤y2x_1 \le i,k \le x_2, \ y_1 \le j,l \le y_2x1≤i,k≤x2, y1≤j,l≤y2. Please help your leader calculate the maximum possible number of cells in such a rectangle so that he'll know how many trees will be planted.
输入描述:
The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤1000)T \ (1 \le T \le 1000)T (1≤T≤1000), the number of cases.
For each case, the first line of the input contains two integers N (1≤N≤500)N\ (1 \le N \le 500)N (1≤N≤500) and M (0≤M≤105)M\ (0 \le M \le 10^5)M (0≤M≤105). The following N lines each contain N integers, where the j\ j j-th integer in the i\ i i-th line denotes ai,j (1≤ai,j≤105)a_{i,j} \ (1 \le a_{i,j} \le 10^5)ai,j (1≤ai,j≤105).
It is guaranteed that the sum of N3N^3N3 over all cases does not exceed 25⋅10725 \cdot 10^725⋅107. 输出描述:
For each case, print a single integer, the maximum number of cells in a valid rectangle. 示例1
输入
2
2 0
1 2
2 1
3 1
1 3 2
2 3 1
3 2 1 输出
1
4 题目大意：给你N*N的矩阵，每个点都有一个权值，询问这里面最大矩阵 (满足 最大值减最小值 小于 k)；
题目思路：题目中给出 N*N*N 小于 7e6 意思就是 用N^3 复杂度来算。关于中问矩阵求和或者最大最小值的问题，我们可以借鉴最大子矩阵和的思路，我们把一个二维子矩阵压缩为 一个一维矩阵，所以问题就转换成了 求一段最大区间，该区间满足 最大值-最小值不能超过k ，这个我们可以用单调队列来维护： 假设两个数组 a,我们维护一个最小值的队列维护一个最大值的队列。我们知道 单调队列维护最小值的时候 是维护递增序列，而维护最大值时维护的是递减序列，然后 我们可以枚举一个 l ，我们让l首先等于1，让l尽可能的小，我们枚举数组a里面的每个数，遍历单调队列，如果当前maxl-minl>k 说明 当前队列不符合要求，我们直接让l++(试图让maxl变小或者minl变大)，判断l是否超过队列首元素的下标，超过就会更新。代码如下：
int l=1,s1=1,s2=1,t1=0,t2=0;
for(int r=1;r<=n;r++)
{
while(s1<=t1&&MAX[r]>=MAX[q1[t1]]) t1--;
q1[++t1]=r;//维护最大值
while(s2<=t2&&MIN[r]<=MIN[q2[t2]]) t2--;
q2[++t2]=r;
while(l<=r&&MAX[q1[s1]]-MIN[q2[s2]]>m)
{
l++;
if(l>q1[s1]) s1++;
if(l>q2[s2]) s2++;
}
ans=max(ans,ll((r-l+1)*(k-i+1)));
} 这里有一个很好玩的运用，可能有些人拐不过来，就是枚举一个l就够了，因为区间的r往后移了之后，他不需要遍历l之前的，因为l之前的绝对不满足条件(maxl-minl>k)。
所以我们每次都把 从第 i 行到 第k 行的矩阵压缩，使得他成为一个队列，然后分别维护最大值与最小值 最后最长的长度就是 r-l+1。size=(r-l+1) *(k-i+1)
这里优化了一下 ，枚举第i行到第k行时，终点一直枚举到n相当于每次加一行，就会少写一层for循环，具体看一下代码叭：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e7+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
ll mp[505][505];
ll MAX[1005],MIN[1005];
int q1[1005],q2[1005];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ll ans=-INF;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++) scanf("%lld",&mp[i][k]);
for(int i=1;i<=n;i++)//这是起点
{
for(int k=1;k<=n;k++) MAX[k]=-INF,MIN[k]=INF;
for(int k=i;k<=n;k++)//这是终点
{
for(int j=1;j<=n;j++)
{
MAX[j]=max(MAX[j],mp[k][j]);
MIN[j]=min(MIN[j],mp[k][j]);
}
int l=1,s1=1,s2=1,t1=0,t2=0;
for(int r=1;r<=n;r++)
{
while(s1<=t1&&MAX[r]>=MAX[q1[t1]]) t1--;
q1[++t1]=r;//维护最大值
while(s2<=t2&&MIN[r]<=MIN[q2[t2]]) t2--;
q2[++t2]=r;
while(l<=r&&MAX[q1[s1]]-MIN[q2[s2]]>m)
{
l++;
if(l>q1[s1]) s1++;
if(l>q2[s2]) s2++;
}
ans=max(ans,ll((r-l+1)*(k-i+1)));
}
}
}
printf("%lld\n",ans);
}
return 0;
}
总结：对于求最大子矩阵的最值或者和，可以考虑用压缩矩阵来做！
京公网安备 11010502036488号