首页 > 代码库 > HDU 2870 Largest Submatrix

HDU 2870 Largest Submatrix

2024-07-14 18:58:40   217人阅读

这三道题的关系是这样的，1505是1506的加强版，2870又是1505的加强版

如果按照上面由简到易的顺序来做的话，还是很简单的

这道题的思想就是 枚举+DP

因为某些字符可以变值，所以我们枚举a, b, c三个矩阵

分别求出对应的h数组以及最大子矩阵，再在里面求出一个最大值即可。

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 1010; 9 char map[maxn][maxn];10 int h[3][maxn], l[3][maxn], r[3][maxn];11 12 int main(void)13 {14     #ifdef LOCAL15         freopen("2870in.txt", "r", stdin);16     #endif17 18     int row, col;19     while(scanf("%d%d", &row, &col) == 2)20     {21         int i, j, k, t;22         for(i = 0; i < row; ++i)23             scanf("%s", map[i]);24         memset(h, 0, sizeof(h));25         int ans = 0;26         for(i = 0; i < row; ++i)27         {28             for(j = 0; j < col; ++j)29             {30                 switch(map[i][j])31                 {    //处理h数组32                     case ‘a‘:33                         ++h[0][j], h[1][j] = h[2][j] = 0;34                         break;35                     case ‘b‘:36                         ++h[1][j], h[0][j] = h[2][j] = 0;37                         break;38                     case ‘c‘:39                         ++h[2][j], h[0][j] = h[1][j] = 0;40                         break;41                     case ‘w‘:42                         ++h[0][j], ++h[1][j], h[2][j] = 0;43                         break;44                     case ‘x‘:45                         ++h[1][j], ++h[2][j], h[0][j] = 0;46                         break;47                     case ‘y‘:48                         ++h[0][j], ++h[2][j], h[1][j] = 0;49                         break;50                     case ‘z‘:51                         ++h[0][j]; ++h[1][j], ++h[2][j];52                 }53             }54             l[0][0] = l[1][0] = l[2][0] = 0;55             r[0][col-1] = r[1][col-1] = r[2][col-1] = col-1;56             for(j = 1; j < col; ++j)57                 for(k = 0; k < 3; ++k)58                 {59                     t = j;60                     while(t > 0 && h[k][j] <= h[k][t-1])61                         t = l[k][t-1];62                     l[k][j] = t;63                 }64 65             for(j = col-2; j >= 0; --j)66                 for(k = 0; k < 3; ++k)67                 {68                     t = j;69                     while(t < col-1 && h[k][j] <= h[k][t+1])70                         t = r[k][t+1];71                     r[k][j] = t;72                 }73 74             for(j = 0; j < col; ++j)75                 for(k = 0; k < 3; ++k)76                     ans = max(ans, (r[k][j]-l[k][j]+1)*h[k][j]);77         }78         printf("%d\n", ans);79     }80     return 0;81 }
代码君

 


联系
我们