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

题目传送门

题意：给出一个01矩阵，找出一条对角线，使得对角线上的元素都为1，而对角线所在矩阵其他元素均为0，使得这样的对角线最长。

---

状态：$f[i][j]$表示以($i$,$j$)为对角线端点的最长长度。（很好想（吧））。

但是本题要求只能对角线上为1，其他地方为0，这样让我们的转移就很难搞。

看到dalao开出了两个辅助数组：$l[i][j]$，$u[i][j]$。分别表示向左/右最多能延伸多少格子使格子中的数为0，向上/下最多能延伸多少格子使格子中的数为0。

那么只要两遍dp，一遍左上到右下，一遍右上到左下即可。

转移有：$f[i][j]$=$min$($f[i-1][j+1]+1$,$min$($l[i][j+1]$,$u[i-1][j]$)$+1$);

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

Code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define maxn 2600

 using namespace std;

 int n,m,ans;

 int mapp[maxn][maxn],l[maxn][maxn],u[maxn][maxn],f[maxn][maxn];

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

         {

             scanf("%d",&mapp[i][j]);

             if(!mapp[i][j]) l[i][j]=l[i][j-]+,u[i][j]=u[i-][j]+;

             else f[i][j]=min(f[i-][j-]+,min(l[i][j-],u[i-][j])+);

             ans=max(ans,f[i][j]);

         }

     memset(f,,sizeof(f));

     memset(l,,sizeof(l));

     memset(u,,sizeof(u));

     for(int i=;i<=n;i++)

         for(int j=m;j>=;j--)

         {

             if(!mapp[i][j]) l[i][j]=l[i][j+]+,u[i][j]=u[i-][j]+;

             else f[i][j]=min(f[i-][j+]+,min(l[i][j+],u[i-][j])+);

             ans=max(ans,f[i][j]);

         }

     printf("%d\n",ans);

     return ;

 }