P2216 [HAOI2007]理想的正方形

admin

https://www.luogu.org/problemnew/show/P2216

题目描述
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入输出格式
输入格式：
第一行为3个整数，分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式：
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例
输入样例#1：
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例#1：
1
说明
问题规模

（1）矩阵中的所有数都不超过1,000,000,000

（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10

（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100

吴语林

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <vector>
   
7. using namespace std;
   
8. int n,m,l,k,p,a[1010][1010],f[1010][1010][11]={0},g[1010][1010][11]={0};
   
9. int main()
   
10. {
    
11.         scanf("%d%d%d",&n,&m,&l);
    
12.         for(int i=0;i<n;i++)
    
13.                 for(int j=0;j<m;j++)
    
14.                 {
    
15.                         scanf("%d",&a[i][j]);
    
16.                         f[i][j][0]=g[i][j][0]=a[i][j];
    
17.                 }
    
18.         for(k=0,p=1;p+p<=l;p*=2,k++)
    
19.                 for(int i=0;i+p+p<=n;i++)
    
20.                         for(int j=0;j+p+p<=m;j++)
    
21.                                 f[i][j][k+1]=max(max(f[i][j][k],f[i+p][j][k]),max(f[i][j+p][k],f[i+p][j+p][k])),g[i][j][k+1]=min(min(g[i][j][k],g[i+p][j][k]),min(g[i][j+p][k],g[i+p][j+p][k]));
    
22.         int ans=999999999;
    
23.         for(int i=0;i+l<=n;i++)
    
24.                 for(int j=0;j+l<=m;j++)
    
25.                 {
    
26.                         int x=i+l-p,y=j+l-p;
    
27.                         int F=max(max(f[i][j][k],f[x][j][k]),max(f[i][y][k],f[x][y][k])),G=min(min(g[i][j][k],g[x][j][k]),min(g[i][y][k],g[x][y][k]));
    
28.                         ans=min(ans,F-G);
    
29.                 }
    
30.         printf("%d",ans);
    
31.         return 0;
    
32. }

复制代码