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

分享图片
 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
相关文章
相关标签/搜索