社区讨论

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

P1736创意吃鱼法参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6tj6h7
此快照首次捕获于
2025/11/20 10:34
4 个月前
此快照最后确认于
2025/11/20 10:34
4 个月前
查看原帖
这种方法,还能优化吗,最后一个点TLE,第九个点880ms(没T),
CPP
#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;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...