P4147 玉蟾宫

给定一个 \(N * M\) 的矩阵

求最大的全为 \(F\) 的子矩阵

Solution

悬线法

限制条件为转移来的和现在的都为 \(F\)

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define REP(i, x, y) for(int i = (x);i <= (y);i++)using namespace std;int RD(){ int out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const int maxn = 2019;int lenx, leny;int map[maxn][maxn];int l[maxn][maxn], r[maxn][maxn];int up[maxn][maxn];int ans;void init(){ lenx = RD(), leny = RD(); REP(i, 1, lenx)REP(j, 1, leny){ char s[19]; scanf("%s", s); if(s[0] == 'F'){ map[i][j] = 1; l[i][j] = r[i][j] = j; up[i][j] = 1; } } REP(i, 1, lenx)REP(j, 2, leny){ if(map[i][j] && map[i][j - 1])l[i][j] = l[i][j - 1]; } REP(i, 1, lenx)for(int j = leny - 1;j >= 1;j--){ if(map[i][j] && map[i][j + 1])r[i][j] = r[i][j + 1]; } }void solve(){ REP(i, 1, lenx)REP(j, 1, leny){ if(!map[i][j])continue; if(i > 1 && map[i - 1][j]){ l[i][j] = max(l[i][j], l[i - 1][j]); r[i][j] = min(r[i][j], r[i - 1][j]); up[i][j] = up[i - 1][j] + 1; } int a = r[i][j] - l[i][j] + 1; ans = max(ans, a * up[i][j]); } printf("%d\n", ans * 3); }int main(){ init(); solve(); return 0; }