P1169-[ZJOI2007]棋盘制作

太过爱你忘了你带给我的痛 2023-06-01 08:53 9阅读 0赞

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

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