UVa 10827 - Maximum sum on a torus

时间：2024-08-07 20:04:38

　　题目大意：UVa 108 - Maximum Sum的加强版，求最大子矩阵和，不过矩阵是可以循环的，矩阵到结尾时可以循环到开头。开始听纠结的，想着难道要分情况讨论吗？！就去网上搜，看到可以通过补全进行处理，也是，通过补全一个相同的，问题就迎刃而解了，所以把n*n的矩阵扩展成2n*2n的矩阵就好了。

 #include <cstdio>

 #include <cstring>

 #define MAXN 160

 int a[MAXN][MAXN], sum[MAXN][MAXN];

 int main()

 {

 #ifdef LOCAL

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

 #endif

     int T;

     scanf("%d", &T);

     while (T--)

     {

         int n;

         scanf("%d", &n);

         memset(sum, , sizeof(sum));

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

         {

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

                 scanf("%d", &a[i][j]);

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

                 a[i][j] = a[i][j-n];

         }

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

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

                 a[i][j] = a[i-n][j];

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

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

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

         int max = a[][];

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

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

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

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

                     {

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

                         if (t > max)   max = t;

                     }

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

     }

     return ;

 }

相关文章