P1736-创意吃鱼法

怼烎@ 2023-06-01 08:51 14阅读 0赞

1 #include <bits/stdc++.h>
     2 #define maxn 13003
     3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     4 typedef long long ll;
     5 using namespace std;
     6 inline ll read()
     7 {
     8     ll ans = 0;
     9     char ch = getchar(), last = ' ';
    10     while(!isdigit(ch)) last = ch, ch = getchar();
    11     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    12     if(last == '-') ans = -ans;
    13     return ans;
    14 }
    15 inline void write(ll x)
    16 {
    17     if(x < 0) x = -x, putchar('-');
    18     if(x >= 10) write(x / 10);
    19     putchar(x % 10 + '0');
    20 }
    21 int n,m;
    22 int a[2503][2503];
    23 int dp[2503][2503];
    24 int h[2503][2503];
    25 int d[2503][2503];
    26 int main()
    27 {
    28     n = read(), m = read();
    29     _for(i,1,n+1)
    30         _for(j,1,m+1)
    31             a[i][j] = read();
    32     
    33     for(int i = 1;i < n+1;i ++)
    34     {
    35         h[i][1] = 0;
    36         for(int j = 2;j < m+1;j ++)
    37         {
    38             if(a[i][j-1]==0)
    39                 h[i][j] = h[i][j-1]+1;
    40             else
    41                 h[i][j] = 0;
    42         }
    43     }
    44 
    45     for(int i = 1;i < m+1;i ++)
    46     {
    47         d[1][i] = 0;
    48         for(int j = 2;j < n+1;j ++)
    49         {
    50             if(a[j-1][i]==0)
    51                 d[j][i] = d[j-1][i]+1;
    52             else
    53                 d[j][i] = 0;
    54         }
    55     }
    56     
    57     int rnt = 0;
    58     
    59     _for(i,1,n+1)
    60         _for(j,1,m+1)
    61             if(a[i][j]==1)
    62                 dp[i][j] = min(dp[i-1][j-1],min(d[i][j],h[i][j])) + 1,
    63                 rnt = max(rnt,dp[i][j]);
    64     
    65     memset(h,0,sizeof(h));
    66     memset(dp,0,sizeof(dp));
    67     for(int i = 1;i < n+1;i ++)
    68     {
    69         h[i][m] = 0;
    70         for(int j = m-1;j > 1;j --)
    71         {
    72             if(a[i][j+1]==0)
    73                 h[i][j] = h[i][j+1]+1;
    74             else
    75                 h[i][j] = 0;
    76         }
    77     }
    78     
    79     _for(i,1,n+1)
    80         for(int j = m;j > 0;j --)
    81             if(a[i][j]==1)
    82                 dp[i][j] = min(dp[i-1][j+1],min(d[i][j],h[i][j])) + 1,
    83                 rnt = max(rnt,dp[i][j]);
    84     
    85     write(rnt);    
    86     return 0;
    87 }

转载于:https://www.cnblogs.com/Asurudo/p/11346685.html