华师一附中OI组

标题: P2216 [HAOI2007]理想的正方形 [打印本页]
作者: admin    时间: 2018-5-13 19:51
标题: P2216 [HAOI2007]理想的正方形
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
作者: 吴语林    时间: 2018-7-30 00:02
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2