崩溃!!!提交记录被我刷了几页!(大号+小号)

P1736 创意吃鱼法

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

O(2)+O(3)

暴力变正解


|