우 객 다 교Planting Trees
시간 제한: C / C + + 3 초, 기타 언어 6 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K 64bit IO 포맷:% 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 의 행렬 에서 가장 큰 서브 행렬 을 찾 아 그 중의 요소 와 두 개의 차 이 를 만족 시 키 는 것 은 M 을 초과 하지 않 는 다.
문제 풀이: 매 거 진 행렬 의 상하 계 를 유지 하 는 동시에 이 열의 최소 값 과 최대 값 을 유지 한 다음 에 오른쪽 경 계 를 매 거 진 다음 에 현재 의 오른쪽 경계 에 대해 최소 왼쪽 경 계 를 찾 은 다음 에 상 감 * 상하 계 의 길 이 를 찾 습 니 다. 가장 작은 왼쪽 경 계 를 어떻게 찾 는 지 에 대해 서 는 오른쪽 경 계 를 매 거 진 동시에 두 개의 단조 로 운 대기 열 을 유지 할 수 있 습 니 다. 그 중에서 하 나 는 최소 값 이 증가 하고 다른 하 나 는 차원 을 유지 할 수 있 습 니 다.최대 값 이 점차 줄 어드 는 것 을 보호 합 니 다. 현재 추 가 된 값 이 대기 열 맨 왼쪽 (최대 값 또는 최소 값) 으로 업데이트 되면 (거 리 는 최소 값 으로 업데이트)그리고 이때 차이 가 M 보다 크 면 저 는 최대 치 를 작 게 해 야 합 니 다. 즉, 최소 왼쪽 경 계 를 현재 최대 치 의 아래 표 시 를 하나 더 한 다음 에 이 판단 을 반복 하면 최소 왼쪽 경 계 를 알 수 있 습 니 다. 이렇게 계속 답 을 업데이트 하면 됩 니 다.
#include
using namespace std;
int a[509][509];
int b[509][4];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;ib[k][1]){
tminr--;
}
quemin[tminr]=b[k][1];
indmin[tminr]=k;
tminr++;
}
if(tmaxr==tmaxl){
quemax[tmaxr]=b[k][2];
indmax[tmaxr]=k;
tmaxr++;
}
else{
while(tmaxr!=tmaxl&&quemax[tmaxr-1]m){
// cout<<666<m){
lmin=indmin[tminl]+1;
tminl++;
}
}
else{
while(tmaxl!=tmaxr&&abs(quemax[tmaxl]-quemin[tminl])>m){
lmax=indmax[tmaxl]+1;
tmaxl++;
}
}
}
int p=max(lmin,lmax);
ans=max(ans,(k-p+1)*(j-i+1));
// cout< 좋은 웹페이지 즐겨찾기
