Home | Problems | Discuss | Login

  

n^3都会超?

2096: Maximum Submatrix

windy7926778 | 2006-06-11 22:56:50 | delete | edit
超了 
windy7926778 | 2006-06-11 22:56:39 | delete | edit
#include <stdio.h>
int a[100][100],n,m,max;
int min(int x,int y)
{if(x<=y) return x;
else return y;
}
void tt()
{int p[101][101][101]={0},i,j,k;max=0;
 for(i=0;i<n;i++)
 p[i][0][1]=!a[i][0];
 for(j=0;j<n;j++) for(i=1;i<m;i++) if(a[j][i]==0) {p[j][i][1]=p[j][i-1][1]+1;if(p[j][i][1]>max) max=p[0][i][1];}
 for(i=1;i<n;i++)
     for(j=0;j<m;j++)
         for(k=2;k<=i+1;k++) {
                   p[i][j][k]=min(p[i-1][j][k-1],p[i][j][1]);
                   if(p[i][j][k]*k>max) max=p[i][j][k]*k;}      
}
int main()
{int t,i,j;
 scanf("%d",&t);
 while(t--)
 {scanf("%d%d",&n,&m);
  for(i=0;i<n;i++)
      for(j=0;j<m;j++) scanf("%d",&a[i][j]);
  tt();
  printf("%d\n",max);
 }
 return 0;
} 
windy7926778 | 2006-06-11 03:28:27 | delete | edit
可我的是n^3,却超了
仔细检查下 
saltycookie | 2006-06-10 20:21:19 | delete | edit
不会 
windy7926778 | 2006-06-06 10:57:20 | delete | edit
 

Please login to reply.