【DP五十题】P1736 创意吃鱼法

const int N=2510;
int f[N][N];//记录以i,j为右下角（或左下角）能吸到的最多的鱼
int l[N][N];//记录最多能向左边扩展多少个0
int up[N][N];//记录最多能向上边扩展多少个0
int r[N][N];//记录最多能向右边扩展多少个0
int a[N][N];
int n,m,ans=INT_MIN;

int main(){
#ifdef WIN32
freopen("test.txt","r",stdin);
#endif
rd(n),rd(m);
rep(i,1,n)
rep(j,1,m){
rd(a[i][j]);
}
rep(i,1,n){
rep(j,1,m){
if(a[i][j]==0){
l[i][j]=l[i][j-1]+1;
up[i][j]=up[i-1][j]+1;
}
else if(a[i][j]==1){
f[i][j]=min(f[i-1][j-1],min(l[i][j-1],up[i-1][j]))+1;
}
ans=max(ans,f[i][j]);
}
}
mem(f,0),mem(up,0);
rep(i,1,n){
dwn(j,m,1){
if(a[i][j]==0){
r[i][j]=r[i][j+1]+1;
up[i][j]=up[i-1][j]+1;
}
else if(a[i][j]==1){
f[i][j]=min(f[i-1][j+1],min(r[i][j+1],up[i-1][j]))+1;
}
ans=max(ans,f[i][j]);
}
}
printf("%d",ans);
return 0;
}

【DP五十题】P1736 创意吃鱼法

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11657147.html