# Luogu P1736 创意吃鱼法【dp】By cellur925

\$or\$    \$f[i][j]\$=\$min\$(\$f[i-1][j+1]+1\$,\$min\$(\$l[i][j+1]\$,\$u[i-1][j]\$)\$+1\$);

Code

``` 1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #define maxn 2600
5
6 using namespace std;
7
8 int n,m,ans;
9 int mapp[maxn][maxn],l[maxn][maxn],u[maxn][maxn],f[maxn][maxn];
10
11 int main()
12 {
13     scanf("%d%d",&n,&m);
14     for(int i=1;i<=n;i++)
15         for(int j=1;j<=m;j++)
16         {
17             scanf("%d",&mapp[i][j]);
18             if(!mapp[i][j]) l[i][j]=l[i][j-1]+1,u[i][j]=u[i-1][j]+1;
19             else f[i][j]=min(f[i-1][j-1]+1,min(l[i][j-1],u[i-1][j])+1);
20             ans=max(ans,f[i][j]);
21         }
22     memset(f,0,sizeof(f));
23     memset(l,0,sizeof(l));
24     memset(u,0,sizeof(u));
25     for(int i=1;i<=n;i++)
26         for(int j=m;j>=1;j--)
27         {
28             if(!mapp[i][j]) l[i][j]=l[i][j+1]+1,u[i][j]=u[i-1][j]+1;
29             else f[i][j]=min(f[i-1][j+1]+1,min(l[i][j+1],u[i-1][j])+1);
30             ans=max(ans,f[i][j]);
31         }
32     printf("%d\n",ans);
33     return 0;
34 }```
View Code