UVa 10667 - Largest Block

时间：2022-03-09 16:59:42

　　题目大意：这个也是和UVa 836 - Largest Submatrix差不多，修改一下数据就可以套用代码的。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define MAXN 110

 int mat[MAXN][MAXN], sum[MAXN][MAXN];

 int main()

 {

 #ifdef LOCAL

     freopen("in", "r", stdin);

 #endif

     int T;

     scanf("%d", &T);

     while (T--)

     {

         int n, k;

         scanf("%d%d", &n, &k);

         int r1, c1, r2, c2;

         for (int i = ; i <= n; i++)

             for (int j = ; j <= n; j++)

                 mat[i][j] = ;

         while (k--)

         {

             scanf("%d%d%d%d", &r1, &c1, &r2, &c2);

             for (int i = r1; i <= r2; i++)

                 for (int j = c1; j <= c2; j++)

                     mat[i][j] = -;

         }

         memset(sum, , sizeof(sum));

         for (int i = ; i <= n; i++)

             for (int j = ; j <= n; j++)

                 sum[i][j] = mat[i][j] + sum[i-][j] + sum[i][j-] - sum[i-][j-];

         int ans = ;

         for (int i = ; i <= n; i++)

             for (int j = ; j <= n; j++)

                 for (int p = i; p <= n; p++)

                     for (int q = j; q <= n; q++)

                     {

                         int t = sum[p][q] - sum[p][j-] - sum[i-][q] + sum[i-][j-];

                         ans = max(ans, t);

                     }

         printf("%d\n", ans);

     }

     return ;

 }

相关文章