zhaomingrui @ 2018-04-30 16:52:35
这种方法,还能优化吗,最后一个点TLE,第九个点880ms(没T),
#include<cstdio>
using namespace std;
int n,m,ans;
int fish[2505][2505],eat[2505][2505];
int front[2505][2505],up[2505][2505],back[2505][2505];
int max(int x,int y){
if(x>=y) return x;
else return y;
}
int min(int x,int y){
if(x<=y) return x;
else return y;
}
inline void dp(){
ans=-1;
/*
思路:两条dp;
1.记录某点上及前及后的连续0的数量;
2.记录以i,j为右下角的最大成立正方形。
*/
//1.用front,up,back记录;\
//2.算最大正方形。
//(1)先从左上到右下。
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
{
if(i==1||j==1)
{
eat[j][i]=fish[j][i];
if(fish[j][i]==1) front[j][i]=0,up[j][i]=0;
else front[j][i]=front[j-1][i]+1,up[j][i]=up[j][i-1]+1;
}
else
{
if(fish[j][i]==1) eat[j][i]=min(min(eat[j-1][i-1],front[j-1][i]),up[j][i-1])+1,up[j][i]=0,front[j][i]=0;
else front[j][i]=front[j-1][i]+1,up[j][i]=up[j][i-1]+1;
ans=max(ans,eat[j][i]);
}
}
//(2)从右上到左下;
for(register int i=1;i<=n;++i)
for(register int j=m;j>=1;j--)
{
if(i==1||j==m)
{
eat[j][i]=fish[j][i];
if(fish[j][i]==1) front[j][i]=0,up[j][i]=0;
else front[j][i]=front[j-1][i]+1,up[j][i]=up[j][i-1]+1;
}
else
{
if(fish[j][i]==1)
eat[j][i]=min(min(eat[j+1][i-1],back[j+1][i]),up[j][i-1])+1,back[j][i]=0;
else back[j][i]=back[j+1][i]+1;
}
ans=max(ans,eat[j][i]);
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
scanf("%d",&fish[j][i]);dp();
printf("%d\n",ans);
}
return 0;
}
by かなで @ 2018-04-30 17:06:49
你的快读呢(huaji)
by かなで @ 2018-04-30 17:06:56
@zhaomingrui
by yjxyjx @ 2018-04-30 17:28:15
快速读入了解一下(huaji.jpg
@zhaomingrui
by arfa @ 2018-04-30 18:32:02