bzoj 1047 //1047: [HAOI2007]理想的正方形

bzoj 1047 //1047: [HAOI2007]理想的正方形 //在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=1047

更多题解，详见https://blog.****.net/mrcrack/article/details/90228694BZOJ刷题记录

方法一：朴素算法

20分洛谷https://www.luogu.org/problem/P2216提交

#include <stdio.h>
#define maxn 1010
int a,b,n,mp[maxn][maxn],ans=2000000300;
int max(int a,int b){
   return a>b?a:b;
}
int min(int a,int b){
   return a<b?a:b;
}
int main(){
   int i,j,p,q,mx,mn;
   scanf("%d%d%d",&a,&b,&n);
   for(i=1;i<=a;i++)
       for(j=1;j<=b;j++)
           scanf("%d",&mp[i][j]);
   for(i=1;i+n-1<=a;i++)//此处错写成for(i=1;i-n+1<=a;i++)
       for(j=1;j+n-1<=b;j++){//此处错写成for(j=1;j-n+1<=b;j++){
           mx=-1000000100,mn=1000000100;
           for(p=0;p<=n-1;p++)
               for(q=0;q<=n-1;q++){
                   mx=max(mx,mp[i+p][j+q]);
                   mn=min(mn,mp[i+p][j+q]);
               }
           if(ans>mx-mn)ans=mx-mn;
       }
   printf("%d\n",ans);
   return 0;
}

方法二：动归

40分洛谷https://www.luogu.org/problem/P2216提交

bzoj 1047 //1047: [HAOI2007]理想的正方形

//以下内容摘自https://www.luogu.org/problemnew/solution/P2216   作者: Aisaka1436 更新时间: 2016-10-20 18:54
/*
用maxv(i,j,k)表示以点(i,j)为左上角的边长为k的矩形中的最大值，然后用递推公式
maxv(i,j,k)=max{maxv(i,j,k-1), maxv(i+1,j+1,k-1), maxv(i+1,j,k-1), maxv(i,j+1,k-1)}
*/
//竟然遇到一个   已杀死问题，猜测数组开得过大mx[maxn][maxn][105],mn[maxn][maxn][105]
//int a,b,n,mp[maxn][maxn],ans=2000000300,mx[maxn][maxn][105],mn[maxn][maxn][105];
//1000*1000*100*4/1024/1024=381.5MB
//很无奈，mx[maxn][maxn][105]爆空间，只能改成mx[maxn][maxn][21]，硬着头皮提交。2019-11-4
#include <stdio.h>
#define maxn 1010
int a,b,n,mp[maxn][maxn],ans=2000000300,mx[maxn][maxn][21],mn[maxn][maxn][21];//int a,b,n,mp[maxn][maxn],ans=2000000300,mx[maxn][maxn][105],mn[maxn][maxn][105];
int max(int a,int b){
   return a>b?a:b;
}
int min(int a,int b){
   return a<b?a:b;
}
int main(){
   int i,j,k;
   scanf("%d%d%d",&a,&b,&n);
   for(i=1;i<=a;i++)
       for(j=1;j<=b;j++)
           scanf("%d",&mp[i][j]),mx[i][j][1]=mn[i][j][1]=mp[i][j];
   for(k=2;k<=n;k++)
       for(i=1;i+k-1<=a;i++)
           for(j=1;j+k-1<=b;j++){
               int mmx=-1000000100,mmn=1000000100;
               mmx=max(mx[i][j][k-1],mmx),mmx=max(mx[i+1][j+1][k-1],mmx);
               mmx=max(mx[i+1][j][k-1],mmx),mmx=max(mx[i][j+1][k-1],mmx);
               mmn=min(mn[i][j][k-1],mmn),mmn=min(mn[i+1][j+1][k-1],mmn);
               mmn=min(mn[i+1][j][k-1],mmn),mmn=min(mn[i][j+1][k-1],mmn);
               mx[i][j][k]=mmx,mn[i][j][k]=mmn;
           }
   for(i=1;i+n-1<=a;i++)
       for(j=1;j+n-1<=b;j++)
           if(ans>mx[i][j][n]-mn[i][j][n])ans=mx[i][j][n]-mn[i][j][n];
   printf("%d\n",ans);
   return 0;
}

方法三：动归滚动数组优化

70分洛谷https://www.luogu.org/problem/P2216提交

bzoj 1047 //1047: [HAOI2007]理想的正方形

//以下内容摘自https://www.luogu.org/problemnew/solution/P2216?page=6 作者: cn：苏卿念更新时间: 2018-08-03 10:45
/*

bzoj 1047 //1047: [HAOI2007]理想的正方形

*/
//样例通过，提交70分.2019-11-4
#include <stdio.h>
#define maxn 1010
int a,b,n,mp[maxn][maxn],ans=2000000300,mx[maxn][maxn],mn[maxn][maxn];
int max(int a,int b){
   return a>b?a:b;
}
int min(int a,int b){
   return a<b?a:b;
}
int main(){
   int i,j,k;
   scanf("%d%d%d",&a,&b,&n);
   for(i=1;i<=a;i++)
       for(j=1;j<=b;j++)
           scanf("%d",&mp[i][j]),mx[i][j]=mn[i][j]=mp[i][j];
   for(k=2;k<=n;k++)
       for(i=1;i+k-1<=a;i++)
           for(j=1;j+k-1<=b;j++){
               mx[i][j]=max(mx[i+1][j+1],mx[i][j]),mx[i][j]=max(mx[i+1][j],mx[i][j]),mx[i][j]=max(mx[i][j+1],mx[i][j]);
               mn[i][j]=min(mn[i+1][j+1],mn[i][j]),mn[i][j]=min(mn[i+1][j],mn[i][j]),mn[i][j]=min(mn[i][j+1],mn[i][j]);
           }
   for(i=1;i+n-1<=a;i++)
       for(j=1;j+n-1<=b;j++)
           if(ans>mx[i][j]-mn[i][j])ans=mx[i][j]-mn[i][j];
   printf("%d\n",ans);
   return 0;
}

//1047: [HAOI2007]理想的正方形
//在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=1047
//题目比较简洁，也容易看懂。
//涉及的点有1000*1000=10^6，那么O(nlogn)算法。
//二维RMQ写法是不是有些象二维树状数组。猜。2019-11-3 22:10
//https://www.luogu.org/problemnew/solution/P2216
//

bzoj 1047 //1047: [HAOI2007]理想的正方形

相关推荐